Complexity Dojo/Ladner's Theorem
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.