How are all NP Complete problems similar?

Problem Detail: 

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

1. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified in polynomial time.
2. Take any known NP-complete problem (call "Easy") and reduce all of it's instances to few instances of given problem (call "Hard"). Note this is not necessarily an 1:1 mapping.
3. Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP-complete problem in polynomial time, then all NP-complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?

Asked By : Ankush

Answered By : Florian Speelman

Your question seems to come from the fact that you're not immediately convinced that the current problem can't be harder. The current problem can't be harder than any NP-complete problem because it is in NP.

If you want to be convinced that the notion of NP-completeness even exists (i.e. that you can reduce anything in NP to an NP-complete problem) you should study the Cook-Levin theorem which states that SAT is NP-complete.

Since NP-completeness states something about being the target of a reduction from any problem in NP, the proof works by encoding the Turing machine which was the verifier of the original problem as a formula. This formula is satisfiable if and only if there exists an input which lets the Turing machine accept. You could in principle use this proof to reduce your current problem to SAT, and after that to every other NP-complete problem via transitivity of polynomial-time reductions.

(I actually wanted to just add a link to the Cook-Levin theorem in a comment, but this is my first stackexchange post and I think it doesn't let me comment yet.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3226