# 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.