# Are all the NP-complete problems have strong reductions?

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?

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