Why Every P Problem Reduces to Any Nontrivial NP-Complete Problem
At a glance
- 1. Fix the reduction
Interpret reducible as polynomial-time many-one reducible: map inputs while preserving yes and no answers.
- 2. Choose target instances
Select one fixed yes-instance and one fixed no-instance of the target problem.
- 3. Decide the source
Run the polynomial-time algorithm for the source problem on the input.
- 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 to language , written , is a polynomial-time computable function such that, for every input ,
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 to shows that an algorithm for can be used to decide .
Proof
Let , and let be any nontrivial language. “Nontrivial” means that there are strings and with and . Choose and fix such strings.
Because is in P, there is a deterministic polynomial-time algorithm that decides whether an input belongs to . Define the function as follows:
To compute , run the algorithm for and output either or . The decision takes polynomial time, and writing one of two fixed strings takes constant time. Thus is polynomial-time computable. If , then ; if , then . Therefore,
so .
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 be 2-SAT, which is in P, and let be 3-SAT, an NP-complete problem. Choose a fixed satisfiable 3-CNF formula, such as , and a fixed unsatisfiable 3-CNF formula, such as . If your definition requires each clause to have exactly three literals, repeat literals in the unit clauses: .
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 when is in P and is nontrivial. It does not establish .
- Forgetting that the target must be nontrivial. If is the empty language, no input can map to a yes-instance; if 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
- Introduction to the Theory of Computation — Michael Sipser
- 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.