Ladner's theorem

Remarks

Such languages are called NP-intermediate. The proof is a delayed diagonalization due to Richard Ladner, published in 1975. One builds $L$ from SAT by keeping the instances of some input lengths and removing those of the other lengths. The pattern of lengths is chosen in stages, so that each polynomial-time machine fails to decide $L$ and each polynomial-time reduction fails to reduce SAT to $L$. The language obtained is in NP, and it is not complete for NP under polynomial-time reductions.

The theorem gives an artificial language. Natural candidates for NP-intermediate problems are graph isomorphism and the decision version of integer factorization, but none is proved to be NP-intermediate, since that would imply $\mathrm{P} \ne \mathrm{NP}$. The hypothesis cannot be dropped: if $\mathrm{P} = \mathrm{NP}$, then every language in NP other than $\emptyset$ and $\Sigma^*$ is NP-complete.

Going deeper

For a student

The theorem is the reason that problems such as graph isomorphism can be studied as candidates for an intermediate status. Its proof generalizes: the same method shows that between any two languages $A <_p B$ with $B$ decidable there is a third, strictly between them. It contrasts with dichotomy theorems for restricted families, such as Schaefer's theorem for Boolean constraint problems, where no intermediate case occurs.