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
@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.
64.3k questions
77.9k answers
244k comments
80.0k users