Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 59 ยท Complexity

Polynomial-Time Reductions

Understand polynomial-time many-one reductions, how to read A <=p B, and why reductions transfer hardness. Test Partition to Subset Sum and Clique to Independent Set.

How do you show that a new problem is hard without proving anything about every possible algorithm? You use a trick that appears everywhere in theory: reduction. If you can turn any instance of a problem you already know to be hard into an instance of the new problem, then the new problem must be at least as hard. Anyone who solved the new problem quickly would solve the old one quickly too.

You already met reductions in the decidability chapters, where mapping reductions proved that problems are undecidable. Complexity theory uses the same idea with one extra requirement: the translation itself has to be fast, namely polynomial time.

The definition

A language A is polynomial-time (many-one) reducible to a language B, written A โ‰คp B, if there is a function f computable in polynomial time such that for every string w:

TEXT
w โˆˆ A  โ‡”  f(w) โˆˆ B

The function f is the reduction. It maps yes-instances of A to yes-instances of B and no-instances of A to no-instances of B. It does not need to solve anything; it only translates the question.

flowchart LR
    W["Instance w of A"] --> F["f<br/>poly-time translation"]
    F --> FW["Instance f(w) of B"]
    FW --> SB["Any solver for B"]
    SB --> ANS["Same yes/no answer<br/>for w in A"]

A solver for B plus the fast translation f gives a solver for A.

Why reductions transfer hardness

Read A โ‰คp B as "A is no harder than B, up to polynomial overhead". Two facts follow immediately.

  • If B is in P, then A is in P. Compute f(w) in polynomial time, then run the polynomial-time decider for B on it. A composition of polynomial functions is polynomial.
  • If B is in NP, then A is in NP. Translate the instance, then verify a certificate for the translated instance.

The contrapositive is the one we use for hardness: if A is known to be hard (not in P, or NP-hard) and A โ‰คp B, then B is hard too. That is why you always reduce from the known hard problem to the new problem, never the other way around. Getting the direction wrong is the most common mistake in this topic.

To prove B is hard, reduce a known hard problem A to B (A โ‰คp B). Reducing B to A only shows that B is as easy as A, which proves nothing about B being hard.

Reductions are also transitive: A โ‰คp B and B โ‰คp C give A โ‰คp C, since composing two polynomial-time functions gives another. That makes it possible to build long chains from one anchor problem, which is how thousands of problems were shown NP-complete.

Three requirements for every reduction

Whenever you design a reduction A โ‰คp B check all three:

  1. f is computable in polynomial time. A translation that itself takes exponential time is useless.
  2. Yes maps to yes. If w is a yes-instance of A, then f(w) is a yes-instance of B.
  3. No maps to no (or, equivalently, yes-instances of f(w) come only from yes-instances of w). If f(w) is a yes-instance of B, then w must have been a yes-instance of A.

Forgetting the second half of the "if and only if" is the typical error in proofs.

Example 1: Partition reduces to Subset Sum

PARTITION: given a list of positive integers, can it be split into two groups with equal sums? SUBSET-SUM: given a list of positive integers and a target t, is there a subset that adds up to t?

The reduction: given (a1, ..., an) for PARTITION, let S = a1 + ... + an. If S is odd, output a fixed no-instance of SUBSET-SUM (for example the list [1] with target 2). Otherwise output the same list with target S / 2. One pass over the list is enough, so f is polynomial. A subset with sum S/2 exists exactly when the rest also sums to S/2.

Python Reducing Partition to Subset Sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both routes always agree, which is the "if and only if" in action. The check is empirical rather than a proof, but it is a good habit: test every reduction on small random instances against a brute-force solver before trusting it.

Example 2: Clique reduces to Independent Set

A clique of size k is a set of k vertices that are all pairwise adjacent. An independent set of size k is a set of k vertices with no two adjacent. The two properties are mirror images: a set is a clique in G exactly when it is an independent set in the complement graph G' (the graph with an edge exactly where G has none).

So the reduction maps (G, k) to (G', k). Building G' means looking at each of the n^2 vertex pairs once, which is polynomial.

Python Clique to Independent Set via the complement graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Other kinds of reduction

What we used is a many-one (Karp) reduction: one call to a solver for B, and its answer is passed through unchanged. There is also the Turing (Cook) reduction, where an algorithm for A may call an oracle for B many times and combine the answers in any way. Cook reductions are more flexible; Karp reductions are stricter and are the standard for defining NP-completeness. A third variant, the log-space reduction, requires f to use only logarithmic memory, and it is used for finer distinctions inside P.

Designing a reduction: a checklist

  • Write down both problems with their exact input and question.
  • Find a natural correspondence between structures: clique and independent set, assignment and vertex choice.
  • Describe f as an algorithm that builds the new instance piece by piece (a "gadget" for each variable or clause).
  • Argue forward (yes goes to yes) and backward (yes comes only from yes).
  • Count the size of f(w) and the time to build it: polynomial.

You will use this exact checklist in the next lessons, when we reduce SAT to other problems.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. If A is polynomial-time reducible to B (A โ‰คp B) and B is in P, what follows?

    Translate in polynomial time and run the polynomial-time decider for B. The composition is polynomial, so A is in P.
  2. 2. To prove a new problem X is NP-hard, which reduction do you build?

    Hardness flows from the known hard problem to the new one: if X were easy, the known hard problem would be easy as well.
  3. 3. Which condition must a polynomial-time many-one reduction f satisfy?

    The if-and-only-if statement is the defining property. Yes-instances map to yes-instances and no-instances map to no-instances.
  4. 4. Why does the complement graph reduce CLIQUE to INDEPENDENT-SET?

    Pairs adjacent in G are non-adjacent in the complement and vice versa, so cliques and independent sets swap roles with the same size k.

Summary

  • A โ‰คp B means a polynomial-time function f with w โˆˆ A โ‡” f(w) โˆˆ B.
  • Reductions carry easiness down (B in P implies A in P) and hardness up (A hard implies B hard).
  • Always reduce from the known hard problem to the new one, and prove both directions.
  • Reductions compose, so chains of them spread hardness across many problems.
  • Karp (many-one) reductions define NP-completeness; Cook (oracle) reductions are more general.

Next: NP-Completeness and the Cook-Levin Theorem