NP-intermediate
Lua error in package.lua at line 80: module 'strict' not found. 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 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. Since the other direction is trivial, we can say 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 can not be in NPI.[2] Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm.[3]
List of problems that might be NP-intermediate[4]
- Factoring integers
- Isomorphism problems: Graph isomorphism problem, Group isomorphism problem, Group automorphism, Ring isomorphism, Ring automorphism
- Computing the rotation distance[5] between two binary trees or the flip distance between two triangulations of the same convex polygon
- The turnpike problem[6] of reconstructing points on line from their distance multiset
- Discrete Log Problem and others related to cryptographic assumptions
- Determining winner in parity games[7]
- Determining who has the highest chance of winning a stochastic game[7]
- Numbers in boxes problems[8]
- Agenda control for balanced single-elimination tournaments[9]
- Knot triviality[10]
- Assuming NEXP is not equal to EXP, padded versions of NEXP-complete problems
- Problems in TFNP[11]
- Intersecting Monotone SAT[12]
- Minimum Circuit Size Problem[13][14]
- Deciding whether a given triangulated 3-manifold is a 3-sphere
- The cutting stock problem with a constant number of object lengths[15]
- Monotone self-duality[16]
- Planar minimum bisection[17]
- Pigeonhole subset sum[18]
- Determining the result of a comparison between two sums of square roots of integers[19]
- Deciding whether a graph admits a graceful labeling[20]
- Gap version of the closest vector in lattice problem[21]
- The linear divisibility problem[22]
- Finding the VC dimension[23]
- Clustered planarity[24]
References
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237
- ↑ Rotation distance, triangulations, and hyperbolic geometry
- ↑ Reconstructing sets from interpoint distances
- ↑ 7.0 7.1 http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
- ↑ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106
- ↑ On total functions, existence theorems and computational complexity
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ http://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950
- ↑ Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
- ↑ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806
- ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
External links
- Complexity Zoo: Class NPI
- Basic structure, Turing reducibility and NP-hardness
- Lua error in package.lua at line 80: module 'strict' not found.
