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

Mapping Reductions

Understand mapping (many-one) reductions and how they transform instances of one problem into another in polynomial time.

Mapping Reductions

You'll learn how to formally transform one problem into another to compare their computational difficulty.

In complexity theory, a mapping reduction (also called a many-one reduction) is a technique where you convert every instance of problem A into an instance of problem B using a transformation function. If you can solve B, you automatically solve A by first applying the transformation.

The Core Idea

Think of it like translation: if you want to know whether a French sentence is grammatically correct, but you only have an English grammar checker, you could translate the French to English first. If you can translate any French sentence to English quickly (in polynomial time), and the English checker works, you've solved the French problem via the English one.

Formally, we say problem A reduces to problem B (written A ≤_m B) if there exists a polynomial-time computable function f that maps:

  • Every "yes" instance of A to a "yes" instance of B
  • Every "no" instance of A to a "no" instance of B

Why This Matters

Mapping reductions let us prove relationships between problems:

  • If A reduces to B and B is easy (in P), then A is also easy
  • If A reduces to B and A is hard (NP-complete), then B is at least as hard

This is how we build the chain of NP-complete problems: we reduce SAT to 3-SAT, 3-SAT to Clique, Clique to Vertex Cover, and so on. Each reduction proves the target problem is at least as hard as the source.

The polynomial-time requirement is crucial—it ensures the transformation itself doesn't add unreasonable complexity.

Key Takeaway: Mapping reductions transform problem instances in polynomial time, preserving yes/no answers, allowing us to compare computational difficulty and prove hardness results.