NP-intermediate

From Wikipedia, the free encyclopedia
  (Redirected from Ladner's theorem)
Jump to navigation Jump to 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 E. 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, 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.[2][3] Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm.[4]

List of problems that might be NP-intermediate[5][edit]

Algebra and number theory[edit]

Boolean logic[edit]

Computational geometry and computational topology[edit]

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

Game theory[edit]

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

Graph algorithms[edit]

Miscellaneous[edit]

References[edit]

  1. ^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM. 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. ^ Schaefer, Thomas J. (1978). "The complexity of satisfiability problems" (PDF). Proc. 10th Ann. ACM Symp. on Theory of Computing. pp. 216–226. MR 0521057.
  4. ^ "Problems Between P and NPC". Theoretical Computer Science Stack Exchange. 20 August 2011. Retrieved 1 November 2013.
  5. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237
  6. ^ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
  7. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331
  8. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739
  9. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745
  10. ^ 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
  11. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950
  12. ^ Rotation distance, triangulations, and hyperbolic geometry
  13. ^ Reconstructing sets from interpoint distances
  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/1106#1106
  16. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806
  17. ^ Demaine, Erik D.; O'Rourke, Joseph (2007), "24 Geodesics: Lyusternik–Schnirelmann", Geometric folding algorithms: Linkages, origami, polyhedra, Cambridge: Cambridge University Press, pp. 372–375, doi:10.1017/CBO9780511735172, ISBN 978-0-521-71522-5, MR 2354878.
  18. ^ a b http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
  19. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460
  20. ^ Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
  21. ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384
  22. ^ Cortese, Pier Francesco; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Pizzonia, Maurizio (2008), "C-planarity of C-connected clustered graphs", Journal of Graph Algorithms and Applications, 12 (2): 225–262, doi:10.7155/jgaa.00165, MR 2448402.
  23. ^ Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms, 42: 69–108, doi:10.1006/jagm.2001.1195.
  24. ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete", SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, MR 2519936.
  25. ^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Simultaneous graph embeddings with fixed edges", Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers, Lecture Notes in Computer Science, 4271, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, MR 2290741.
  26. ^ On total functions, existence theorems and computational complexity
  27. ^ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
  28. ^ Papadimitriou, Christos H.; Yannakakis, Mihalis (1996), "On limited nondeterminism and the complexity of the V-C dimension", Journal of Computer and System Sciences, 53 (2, part 1): 161–170, doi:10.1006/jcss.1996.0058, MR 1418886

External links[edit]