MathLabs
TheoremProved

One easy NP-complete problem collapses P and NP

Statement

If BB is NP-complete and B∈PB \in P, then P=NPP = NP.

Why is it true?

NP-completeness of BB means every NP problem can be rewritten, in polynomial time, as an instance of BB. If BB 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 BB is NP-complete and there is an algorithm solving BB in time O(nk1)O(n^{k_1}). Take any A∈NPA \in NP; by NP-completeness of BB, A≤pBA \le_p B, meaning there is a reduction function ff computable in time O(nk2)O(n^{k_2}) that maps instances of AA to instances of BB while preserving yes/no answers.

On an input xx of length nn for AA, first compute f(x)f(x): this takes time O(nk2)O(n^{k_2}), and in particular the output f(x)f(x) has length at most O(nk2)O(n^{k_2}) (a polynomial-time algorithm cannot write more output than time it runs). Then run the polynomial-time algorithm for BB on f(x)f(x): since ∣f(x)∣=O(nk2)|f(x)| = O(n^{k_2}), this takes time O((nk2)k1)=O(nk1k2)O\big((n^{k_2})^{k_1}\big) = O(n^{k_1 k_2}).

The total running time is O(nk2)+O(nk1k2)=O(nk1k2)O(n^{k_2}) + O(n^{k_1 k_2}) = O(n^{k_1 k_2}), still a polynomial in nn (the composition of two polynomials is a polynomial). By the correctness of the reduction, xx is a yes-instance of AA if and only if f(x)f(x) is a yes-instance of BB, so this combined procedure correctly decides AA in polynomial time.

Since A∈NPA \in NP was arbitrary, every NP problem has a polynomial-time algorithm, i.e. NP⊆PNP \subseteq P. Combined with the always-true containment P⊆NPP \subseteq NP, this gives P=NPP = NP.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Stephen A. Cook (1971). The Complexity of Theorem-Proving Procedures · DOI:10.1145/800157.805047
  2. Michael Sipser (2012). Introduction to the Theory of Computation
  3. Michael R. Garey, David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness
  4. Clay Mathematics Institute (2000). P vs NP Problem