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?

  • 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.