Are all the NP-complete problems have strong reductions? If I find a polynomial solution to one NP-complete problem, can I state that P = NP?
$\begingroup$
$\endgroup$
-
1$\begingroup$ yes, if you show that one of the NP-complete problems is in P P=NP $\endgroup$ – abc Nov 24 '13 at 8:50
$\begingroup$
$\endgroup$
You don't seem to have a correct grasp of the concept of NP-completeness. Every NP complete problem has a reduction to every other NP complete problem. That is, there is a poly-time reduction from SAT to HAMPATH.
Thus, if you have a polynomial solution for HAMPATH, you can solve any case of SAT in polynomial time, so P=NP.
-
$\begingroup$ How do you prove that a problem is NP complete? Do you need to do a reduction from all other problems? There are thousands of them. $\endgroup$ – Ilya Gazman Nov 24 '13 at 9:15
-
6$\begingroup$ That's exactly the beauty of reductions: they are transitive. Once you show on a problem $A$ that it is NP complete, then in order to show that problem $B$ is NP complete, all you need to show is that $B$ is in NP, and that there is a reduction from $A$ to $B$. But how do you get the "first" NP complete problem - well, the Cook-Levin theorem shows a reduction from every problem in NP (there are infinitely many of those, not just thousands) to SAT. $\endgroup$ – Shaull Nov 24 '13 at 9:25
