Polynomial time reduction

Definition

A language (decision problem) A is polynomial-time reducible to a language B, written A ≤p B, if there is a function f : Σ* → Σ* such that

1. f is computable by a deterministic TM in polynomial time, and
2. for every string w: w ∈ A if and only if f(w) ∈ B.

The function f is called a polynomial-time (many-one or Karp) reduction. It transforms every instance of A into an instance of B with the same yes/no answer.

   instance w of A ──f (poly time)──► f(w), an instance of B
        yes/no for w  ==  yes/no for f(w)

Consequences

• If A ≤p B and B ∈ P, then A ∈ P (run f, then the polynomial algorithm for B; a polynomial of a polynomial is a polynomial).
• If A ≤p B and A is NP-hard (or NP-complete), then B is NP-hard. This is how NP-completeness of new problems is shown: reduce a known NP-complete problem to them.
• ≤p is transitive: A ≤p B and B ≤p C give A ≤p C.

Example: 3-SAT ≤p CLIQUE

Given a 3-CNF formula φ with k clauses, build a graph G: one vertex for each literal occurrence in each clause; join two vertices by an edge unless they are in the same clause or are contradictory literals (x and ¬x). Then φ is satisfiable if and only if G has a clique of size k. The construction takes polynomial time, so 3-SAT ≤p CLIQUE, and CLIQUE is NP-hard.