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.