Course contentsShow
← Computer Science
Lesson 1932 of 2,87243. Complexity TheoryFree lesson

Proving NP-Completeness via Reduction

Learn the standard technique for proving a problem is NP-complete by reducing from a known NP-complete problem.

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:

  1. Show B is in NP: Demonstrate that given a solution, you can verify it in polynomial time
  2. 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.