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: 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][edit]

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. ^ Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. p. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001. 
  3. ^ "Problems Between P and NPC". Theoretical Computer Science Stack Exchange. 20 August 2011. Retrieved 1 November 2013. 
  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. ^ 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 
  15. ^ http://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827
  16. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950
  17. ^ Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
  18. ^ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
  19. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010
  20. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384
  21. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806
  22. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331

External links[edit]