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

Polynomial-Time Reductions

Study polynomial-time many-one reductions and their role in defining NP-completeness relationships.

Polynomial-Time Reductions

What you'll learn: You'll understand how polynomial-time many-one reductions formally establish relationships between problems and why they're the foundation of NP-completeness.

The Core Idea

A polynomial-time many-one reduction (often written as ≤_p or ≤_m^p) is a specific type of mapping reduction where the transformation must run in polynomial time. If we can reduce problem A to problem B in polynomial time, we write A ≤_p B, meaning "A is no harder than B."

Here's the formal requirement: There must exist a function f that:

  1. Maps instances of problem A to instances of problem B
  2. Runs in polynomial time
  3. Preserves yes/no answers: instance x is a "yes" for A if and only if f(x) is a "yes" for B

Why Polynomial Time Matters

Think of polynomial-time reductions as "efficient translators." If you can quickly translate one problem into another, solving the second problem efficiently means you can solve the first efficiently too.

The key insight: If A ≤_p B and B is in P, then A is also in P. Conversely, if A ≤_p B and A is not in P, then B cannot be in P either.

Connection to NP-Completeness

Polynomial-time reductions are the backbone of NP-completeness theory. A problem is NP-complete if:

  1. It's in NP
  2. Every problem in NP can be reduced to it in polynomial time

This means if you could solve any NP-complete problem efficiently, you'd solve all NP problems efficiently—the P vs NP question would be answered!

When we reduced 3-SAT to Clique or Hamiltonian Cycle to TSP, we were using polynomial-time many-one reductions to prove hardness.

Key Takeaway: Polynomial-time many-one reductions are efficient, answer-preserving transformations that allow us to compare problem difficulty and formally define NP-completeness through chains of reductions.