in Theory of Computation
870 views
0 votes
0 votes

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is:

Do we also need to prove that problem X can be reduced to at least one NP problem?

According to the definition of NP-completeness, each and every NP problem must be reducible to NP-complete problem. As problem X is NP, are we not supposed to prove that this NP problem can be reduced to other NP-complete problems? Why does this reduction have to be only one way to prove a problem is NP-complete? 

PS: I have already asked this question in cs.stackexchange 

Image describing the problem visually

in Theory of Computation
870 views

4 Comments

No, you have given that Y is in NPC and X is in NP. It already implies X is reducible to Y. Here, we need to prove X as an NPC problem. So,  we need only reduction from Y to X.
0
0
Ok. Then now let's say X is proved to be NP. All the current NP-complete problems will become NP. This is because we don't know whether X is reducible to those previous NP-complete problems. What should be done next?
0
0

@commenter commenter

U mainly want to know, why reduction is one sided.

right?

If we write it in word of math

Say , a set can generate every subset.

But is every subset generate the original set?

Same thing happen here.

 

0
0

Please log in or register to answer this question.

Related questions