One easy NP-complete problem collapses P and NP
Statement
If is NP-complete and , then .
Why is it true?
NP-completeness of means every NP problem can be rewritten, in polynomial time, as an instance of . If itself can then be solved in polynomial time, chaining the rewriting step and the solving step together solves the original NP problem in polynomial time too — so a single tractable NP-complete problem drags every NP problem down into P with it.
Proof sketch
Suppose is NP-complete and there is an algorithm solving in time . Take any ; by NP-completeness of , , meaning there is a reduction function computable in time that maps instances of to instances of while preserving yes/no answers.
On an input of length for , first compute : this takes time , and in particular the output has length at most (a polynomial-time algorithm cannot write more output than time it runs). Then run the polynomial-time algorithm for on : since , this takes time .
The total running time is , still a polynomial in (the composition of two polynomials is a polynomial). By the correctness of the reduction, is a yes-instance of if and only if is a yes-instance of , so this combined procedure correctly decides in polynomial time.
Since was arbitrary, every NP problem has a polynomial-time algorithm, i.e. . Combined with the always-true containment , this gives .
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Stephen A. Cook (1971). The Complexity of Theorem-Proving Procedures · DOI:10.1145/800157.805047
- Michael Sipser (2012). Introduction to the Theory of Computation
- Michael R. Garey, David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness
- Clay Mathematics Institute (2000). P vs NP Problem