Cs · Computer Science

Why Every P Problem Reduces to Any Nontrivial NP-Complete Problem

Published By the 9to5Science editorial team

At a glance

  1. 1. Fix the reduction

    Interpret reducible as polynomial-time many-one reducible: map inputs while preserving yes and no answers.

  2. 2. Choose target instances

    Select one fixed yes-instance and one fixed no-instance of the target problem.

  3. 3. Decide the source

    Run the polynomial-time algorithm for the source problem on the input.

  4. 4. Output the matching instance

    Return the fixed yes-instance for yes inputs and the fixed no-instance otherwise.

The usual interpretation of “every problem in P is reducible” is that every decision problem in P is polynomial-time many-one reducible to any NP-complete problem. The proof is short: use the polynomial-time algorithm for the source problem to choose between two fixed instances of the target. This works for any target language that has at least one yes-instance and one no-instance.

What the reduction means

Treat a decision problem as a language: a set of strings whose members are the yes-instances. A polynomial-time many-one reduction from language AA to language BB, written A≤pBA \leq_p B, is a polynomial-time computable function ff such that, for every input xx,

x∈A  ⟺  f(x)∈B.x \in A \iff f(x) \in B.

The reduction must preserve the answer. It does not have to preserve the input itself, or be one-to-one. The notation’s direction is important: a reduction from AA to BB shows that an algorithm for BB can be used to decide AA.

Proof

Let A∈PA \in \mathrm{P}, and let BB be any nontrivial language. “Nontrivial” means that there are strings yy and nn with y∈By \in B and n∉Bn \notin B. Choose and fix such strings.

Because AA is in P, there is a deterministic polynomial-time algorithm that decides whether an input xx belongs to AA. Define the function ff as follows:

f(x)={y,if x∈A,n,if x∉A.f(x) = \begin{cases} y, & \text{if } x \in A, \\ n, & \text{if } x \notin A. \end{cases}

To compute f(x)f(x), run the algorithm for AA and output either yy or nn. The decision takes polynomial time, and writing one of two fixed strings takes constant time. Thus ff is polynomial-time computable. If x∈Ax \in A, then f(x)=y∈Bf(x)=y \in B; if x∉Ax \notin A, then f(x)=n∉Bf(x)=n \notin B. Therefore,

x∈A  ⟺  f(x)∈B,x \in A \iff f(x) \in B,

so A≤pBA \leq_p B.

Every NP-complete language is nontrivial: it has at least one yes-instance and one no-instance. (A language that contains every string or no strings cannot be NP-hard under polynomial-time many-one reductions.) Consequently, every language in P reduces to every NP-complete language.

Worked example: reducing 2-SAT to 3-SAT

Let AA be 2-SAT, which is in P, and let BB be 3-SAT, an NP-complete problem. Choose a fixed satisfiable 3-CNF formula, such as (u∨v∨w)(u \lor v \lor w), and a fixed unsatisfiable 3-CNF formula, such as (u)∧(¬u)(u) \land (\neg u). If your definition requires each clause to have exactly three literals, repeat literals in the unit clauses: (u∨u∨u)∧(¬u∨¬u∨¬u)(u \lor u \lor u) \land (\neg u \lor \neg u \lor \neg u).

The reduction first decides whether the input 2-CNF formula is satisfiable. If it is, it outputs the fixed satisfiable 3-CNF formula; if it is not, it outputs the fixed unsatisfiable one. This is a valid polynomial-time many-one reduction. It is not a useful way to transform the formula’s structure, but a many-one reduction is required to preserve only the yes/no answer.

Common mistakes

  • Reversing the direction. The proof establishes A≤pBA \leq_p B when AA is in P and BB is nontrivial. It does not establish B≤pAB \leq_p A.
  • Forgetting that the target must be nontrivial. If BB is the empty language, no input can map to a yes-instance; if BB contains every string, no input can map to a no-instance. A reduction from a nontrivial source to either target is impossible.
  • Assuming the reduction proves P = NP. It does not. The easy direction from a problem in P to an NP-complete problem follows by deciding the source directly. The consequential direction would be reducing an NP-complete problem to a problem in P: that would imply P = NP.
  • Using a stronger notion without checking it. The construction proves a polynomial-time many-one reduction. Other reductions, such as parsimonious reductions that preserve the number of solutions, impose extra requirements and do not automatically follow from this argument.

References

  1. Introduction to the Theory of Computation — Michael Sipser
  2. Computational Complexity: A Modern Approach — Sanjeev Arora and Boaz Barak

Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.