Complexity Dojo/Ladner's Theorem

Main Zoo - Complexity Garden - Zoo Glossary - Zoo References - Chris' Complexity Dojo

---

Major Theorems: Cook-Levin - Savitch's - Ladner's - Blum Speedup - Impagliazzo-Widgerson - Toda's - Natural Proofs

Proof Techniques: Diagonalization

Notice: You found a stub belonging to the Complexity Zoo. Please consider expanding it.

We know that P ⊆ NP, so P ≠ NP if and only if this inclusion is proper. A plausible question, then, is whether all problems in NP \ P are NP-complete. Ladner's Theorem, proved in [Lad75], shows that this is not the case: there exist languages which are in NP \ P but are not NP-complete. The set of such problems is denoted by NP-intermediate.

The proof of Ladner's Theorem can be easily modified to imply an infinite structure within NP \ P.

The NP-intermediate language constructed in [Lad75] is artificial. Natural languages believed to be NP-intermediate are Integer Factorization, Graph Isomorphism, and Nash Equilibria.

Theorem (Ladner's Theorem). If P ≠ NP, then NPI is non-empty.

---

Proof: ▪