NP-intermediate

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Another problem in NP that is not known to be in P or NP-complete is the minimum circuit size problem (MCSP). Unlike the above problems, MCSP is believed to be NP-complete. However, proving as much via a many-one reduction will imply circuit lower bounds for E (unless NP is contained in SUBEXP, which is a violation of the exponential time hypothesis). Therefore, proving that MCSP is NP-complete is considered outside of current techniques.[3]

List of problems thought to be NP-intermediate[4][edit]

  • 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 planar point set
  • The Turnpike Problem[6] of reconstructing points on line from distances
  • 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]
  • Deciding whether a given triangulated 3-manifold is a 3-sphere
  • The Cutting Stock Problem with a constant number of object lengths[14]
  • Monotone Self-Duality[15]
  • Planar Minimum Bisection[16]
  • Pigeonhole Subset Sum[17]
  • Square Root Sums[18]
  • Deciding Whether a Graph Admits a Graceful Labeling[19]
  • Gap version of the closest vector in lattice problem[20]
  • The linear divisibility problem[21]
  • Matching preclusion
  • Finding the VC dimension

References[edit]

  1. ^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM (JACM) 22 (1): 155–171. doi:10.1145/321864.321877. 
  2. ^ "Problems Between P and NPC". Theoretical Computer Science Stack Exchange. 20 August 2011. Retrieved 1 November 2013. 
  3. ^ Kabanets, Valentine; Cai, Jin-Yi (2000), "Circuit minimization problem", Proc. 32nd Symposium on Theory of Computing, Portland, Oregon, USA, pp. 73–79, doi:10.1145/335305.335314, ECCC TR99-045 .
  4. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237
  5. ^ Rotation distance, triangulations, and hyperbolic geometry
  6. ^ Reconstructing sets from interpoint distances
  7. ^ a b http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
  8. ^ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
  9. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460
  10. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106
  11. ^ On total functions, existence theorems and computational complexity
  12. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739
  13. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745
  14. ^ http://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827
  15. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950
  16. ^ Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
  17. ^ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
  18. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010
  19. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384
  20. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806
  21. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331

External links[edit]