Ladner's theorem, shown in 1975 by Richard E. Ladner,[1] is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete.
Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting.
It is an open question whether any "natural" problem has the same property: Schaefer's dichotomy theorem provides conditions under which classes of constrained Boolean satisfiability problems cannot be in NPI.
[2][3] Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, and decision versions of factoring and the discrete logarithm.
Under the exponential time hypothesis, there exist natural problems that require quasi-polynomial time, and can be solved in that time, including finding a large disjoint set of unit disks from a given set of disks in the hyperbolic plane,[4] and finding a graph with few vertices that is not an induced subgraph of a given graph.