Polynomial-Time Reduction

A **polynomial-time reduction** solves problem A by transforming its inputs into inputs for problem B and using a solver for B, where both the transformation and the surrounding work run in polynomial time. Writing A ≤ B means 'A reduces to B' — A is *no harder than* B, because an efficient solution for B yields one for A. ## Two main kinds - **Many-one (Karp) reduction** (A ≤ₘᵖ B): a polynomial-time function maps a single instance of A to a single instance of B with the *same* yes/no answer. This is the standard tool for defining NP-completeness. - **Turing (Cook) reduction** (A ≤ₜᵖ B): solves A using a polynomial number of calls to a B-subroutine plus polynomial extra work. It is strictly more general than many-one reduction. ## Proving hardness To prove a new problem is NP-complete, show (1) it is in NP, and (2) a known NP-complete problem reduces to it. Note the direction: reducing a *known-hard* problem *to* the new one transfers the hardness onto it. ## Transitivity Reductions compose: if A ≤ B and B ≤ C then A ≤ C. This lets hardness propagate along chains, which is exactly how Richard Karp's 1972 results spread NP-completeness from SAT to many other problems after the Cook–Levin theorem. ## Why reductions equate difficulty If A ≤ B and B ≤ A, the two problems are equally hard up to polynomial factors — the basis for saying all NP-complete problems are 'the same problem in disguise'.