# Is it possible that P vs NP is not the real problem?

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?

• yes, if you show that one of the NP-complete problems is in P P=NP – abc Nov 24 '13 at 8:50

• 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. – Shaull Nov 24 '13 at 9:25