Proving NP-Completeness via Reduction
What you'll learn: How to prove a new problem is NP-complete by reducing a known NP-complete problem to it.
The Standard Technique
Once we have one NP-complete problem (like SAT from the Cook-Levin Theorem), we can prove other problems are NP-complete through reduction. The idea is beautifully simple: if you can transform a known hard problem into your new problem, then your new problem must be at least as hard.
The Two-Step Recipe
To prove problem B is NP-complete:
- Show B is in NP: Demonstrate that given a solution, you can verify it in polynomial time
- Reduce from a known NP-complete problem A to B: Show that if you could solve B efficiently, you could solve A efficiently too
The reduction works like this: take any instance of problem A and transform it (in polynomial time) into an instance of problem B such that the answer to A is "yes" if and only if the answer to B is "yes."
Why This Works
Think of it like a chain of dominoes. If SAT is hard, and you can convert any SAT problem into a 3-SAT problem, then 3-SAT must be hard too. If you could solve 3-SAT quickly, you'd be able to solve SAT quickly by first converting it. Since we believe SAT is hard, 3-SAT must be hard.
The beauty is that each new NP-complete problem becomes a tool for proving the next one NP-complete. That's why we have a vast library of known NP-complete problems.
Key Takeaway: To prove NP-completeness, show your problem is in NP and reduce from a known NP-complete problem—if the known problem transforms into yours, yours inherits the hardness.