874 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

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
commenter commenter asked Jun 13, 2019
362 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 votes
0 votes
1 answer
2
0 votes
0 votes
1 answer
4
gmrishikumar asked Nov 30, 2018
880 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?