Introduction to Reductions
What you'll learn: You'll understand how reductions allow us to compare the difficulty of computational problems and form the backbone of complexity theory.
What is a Reduction?
A reduction is a transformation that converts one problem into another. Think of it like a recipe translator: if you can convert a French recipe into an English one, and you know how to cook from English recipes, then you can effectively cook French dishes too.
In complexity theory, we say "Problem A reduces to Problem B" if we can transform any instance of A into an instance of B, solve B, and use that solution to solve A. This is written as A ≤ B (A reduces to B).
Why Reductions Matter
Reductions let us compare problem difficulty without solving problems directly:
- If A reduces to B, then B is at least as hard as A
- If B is easy (in P), then A must be easy too
- If A is hard (like an NP-Complete problem), then B must be hard too
This is exactly how we proved problems NP-Complete in previous lessons: we reduced known hard problems (like SAT or 3-SAT) to new problems (like Clique, Vertex Cover, or Hamiltonian Cycle).
The Power of Reductions
Reductions create chains of problem difficulty. When you proved 3-SAT reduces to Clique, you didn't solve either problem—you showed they're equally hard. This technique built the entire catalog of NP-Complete problems from just one (SAT via the Cook-Levin Theorem).
Key Takeaway: Reductions transform one problem into another to compare their computational difficulty; they're the fundamental tool for classifying problems into complexity classes and proving hardness results.