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

Introduction to Reductions

Learn what reductions are, why they're fundamental to complexity theory, and how they compare problem difficulty.

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.