NP-intermediate

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

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. 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
23. 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
24. 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.

External links

• 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.