I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.
- Prove that current problem is NP, i.e., given a certificate, prove that it can be verified in polynomial time.
- 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.
- 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?