# NP-intermediate

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, 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. Since the other direction is trivial, it follows that P = NP if and only if NPI is empty.

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. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm.

## List of problems that might be NP-intermediate

### Computational geometry and computational topology

• Computing the rotation distance between two binary trees or the flip distance between two triangulations of the same convex polygon
• The turnpike problem of reconstructing points on line from their distance multiset
• The cutting stock problem with a constant number of object lengths
• Knot triviality
• Deciding whether a given triangulated 3-manifold is a 3-sphere
• Gap version of the closest vector in lattice problem
• Finding a simple closed quasigeodesic on a convex polyhedron

### Game theory

• Determining winner in parity games
• Determining who has the highest chance of winning a stochastic game
• Agenda control for balanced single-elimination tournaments