NP-intermediate
Sign in to saveAlso known as NPI
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 it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.
~4 min read
Article
9 sectionsContents
- List of problems that might be NP-intermediate
- Algebra and number theory
- Boolean logic
- Computational geometry and computational topology
- Game theory
- Graph algorithms
- Miscellaneous
- References
- External links
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 it is also true that if NPI problems exist, then P ≠ NP, 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, and decision versions of factoring and the discrete logarithm.