Lets assume that I found a polynomial solution for Hamiltonian path problem. It is known that you can reduce this problem to SAT. How ever it will be a special case of SAT. Just the case where there is only one interpretation that satisfies that Boolean formula.

Can you extends this special case for general case? If not, how would you define the NP group now?

Are all the NP-complete problems have a strong reduction? If I solve one NP-complete problem, can I state that I found the solution for P versus NP problem. Or it will brake the very definition of P versus NP as some problems will remind part unsolved.

In one case I know for sure that I found the P versus NP problem solution - If I can find polynomial solution for SAT as it stays in the top of the pyramid. But is it true for all the rest of the problems?

  • 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.

| cite | improve this answer | |
  • $\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.