Polynomial-Time Reductions

Core Idea

A polynomial-time many-one reduction (Karp reduction) from problem A to problem B is a polynomial-time computable function f such that x ∈ A iff f(x) ∈ B. If B has a polynomial-time algorithm, so does A. Polynomial-time reductions are the standard tool for proving NP-hardness: to show a new problem B is NP-hard, reduce a known NP-hard problem to B in polynomial time. This preserves computational hardness upward and solutions downward, enabling systematic comparison of complexity.

How It's Best Learned

Master the 3-SAT to 3-Colorability reduction as a template: understand both the formal gadget construction and why it is correct. Practice building reductions from 3-SAT to other NP-complete problems, always verifying correctness and polynomial-time running time.

Common Misconceptions

• The direction of reduction is crucial and often backwards from intuition: to show B is hard, reduce a known-hard problem *to* B, which shows B must be at least as hard.
• Polynomial-time reductions are more restrictive than Turing reductions used in computability theory; they do not allow multiple adaptive queries.

Explainer

Polynomial-time reductions are the backbone of complexity theory's comparative framework. You have already seen computability reductions, which ask whether one problem is computable given an oracle for another. Polynomial-time reductions sharpen that question: not only can we solve A using B, but we can do the transformation efficiently — in polynomial time. This efficiency requirement is what makes them the right tool for distinguishing tractable from intractable problems.

The formal definition of a Karp reduction (many-one polynomial-time reduction) from A to B is a function f computable in polynomial time such that x ∈ A if and only if f(x) ∈ B. Every instance of A gets mapped to an instance of B such that membership is preserved in both directions. If you can solve B efficiently, then to solve A you just transform the input and run B's algorithm. The key consequence: B being easy makes A easy, so B being hard implies A must also be hard.

This asymmetry in how hardness and ease flow is the hardest conceptual piece. The direction of the arrow A ≤_p B says "A reduces to B," meaning B is at least as hard as A — hardness travels upward, against the arrow. To prove a new problem B is NP-hard, you reduce a known NP-hard problem (like 3-SAT) to B. This shows that an efficient algorithm for B would yield an efficient algorithm for 3-SAT, which would imply P = NP. Since we believe P ≠ NP, no such algorithm for B can exist.

The classic example is the reduction from 3-SAT to 3-Colorability: given a 3-SAT formula, construct a graph (using variable gadgets and clause gadgets) such that the graph is 3-colorable exactly when the formula is satisfiable. The construction runs in polynomial time. This proves 3-Colorability is NP-hard, because if you could color graphs efficiently, you could solve 3-SAT efficiently.

Polynomial-time reductions are more restrictive than the Turing reductions encountered in computability theory. A Turing reduction allows multiple adaptive queries to an oracle; a Karp reduction must produce a single transformed instance. In practice, most NP-hardness proofs use Karp reductions, which also compose: if A ≤_p B and B ≤_p C, then A ≤_p C, allowing chains of reductions across the NP-complete problems.