NP-intermediate
(Redirected from Ladner's theorem)
Jump to navigation
Jump to search
 | Some of this article's listed sources may not be reliable. (October 2015) (Learn how and when to remove this template message) |
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]
Contents
List of problems that might be NP-intermediate[5][edit]
Algebra and number theory[edit]
- Factoring integers
- Discrete Log Problem and others related to cryptographic assumptions
- Isomorphism problems: Group isomorphism problem, Group automorphism, Ring isomorphism, Ring automorphism
- Numbers in boxes problems[6]
- The linear divisibility problem[7]
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]
- Graph isomorphism problem
- Planar minimum bisection[20]
- Deciding whether a graph admits a graceful labeling[21]
- Clustered planarity[22]
- Recognizing leaf powers and k-leaf powers[23]
- Recognizing graphs of bounded clique-width[24]
- Finding a simultaneous embedding with fixed edges[25]
Miscellaneous[edit]
- Assuming NEXP is not equal to EXP, padded versions of NEXP-complete problems
- Problems in TFNP[26]
- Pigeonhole subset sum[27]
- Finding the VC dimension[28]
References[edit]
- ^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM. 22 (1): 155–171. doi:10.1145/321864.321877.
- ^ 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.
- ^ Schaefer, Thomas J. (1978). "The complexity of satisfiability problems" (PDF). Proc. 10th Ann. ACM Symp. on Theory of Computing. pp. 216–226. MR 0521057.
- ^ "Problems Between P and NPC". Theoretical Computer Science Stack Exchange. 20 August 2011. Retrieved 1 November 2013.
- ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237
- ^ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
- ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331
- ^ 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
- ^ 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
- ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950
- ^ Rotation distance, triangulations, and hyperbolic geometry
- ^ Reconstructing sets from interpoint distances
- ^ 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/1106#1106
- ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806
- ^ 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.
- ^ a b http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
- ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460
- ^ Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
- ^ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ On total functions, existence theorems and computational complexity
- ^ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
- ^ 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]
- Complexity Zoo: Class NPI
- Basic structure, Turing reducibility and NP-hardness
- Lance Fortnow (24 March 2003). "Foundations of Complexity, Lesson 16: Ladner's Theorem". Retrieved 1 November 2013.
