1,733 views
0 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

Please log in or register to answer this question.

Position:
Show:

Related questions

0 0 votes
0 0 answers
620
620 views
commenter commenter asked Jun 13, 2019
620 views
I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like...
0 0 votes
1 1 answer
947
947 views
0 0 votes
1 1 answer
1.0k
1.0k views
Harsh Kumar asked Mar 20, 2018
1,016 views
I know that NP-complete problems are the hardest NP problems and every NP problem can be reduced NP-Complete problems in polynomial time. Now, it is said that all NP prob...
0 0 votes
1 answers 1 answer
1.4k
1.4k views
gmrishikumar asked Nov 30, 2018
1,397 views
All the places where I have read the Ham-Cycle problem, the graph used is directed. Is the problem of finding Ham-Cycle on an undirected graph also NP-Complete or not?