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 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 it is also true that if NPI problems exist, then P ≠ NP, 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, and decision versions of factoring and the discrete logarithm.

Under the exponential time hypothesis, there exist natural problems that require quasi-polynomial time, and can be solved in that time, including finding a large disjoint set of unit disks from a given set of disks in the hyperbolic plane,^[4] and finding a graph with few vertices that is not an induced subgraph of a given graph.^[5] The exponential time hypothesis also implies that no quasi-polynomial-time problem can be NP-complete, so under this assumption these problems must be NP-intermediate.

List of problems that might be NP-intermediate

Algebra and number theory

A decision version of factoring integers: for input $n$ and $k$ , does $n$ have a factor in the interval $[2,k]$ ?
Decision versions of the discrete logarithm problem and others related to cryptographic assumptions
Linear divisibility: given integers $x$ and $y$ , does $y$ have a divisor congruent to 1 modulo $x$ ?^[6]^[7]

Boolean logic

IMSAT, the Boolean satisfiability problem for "intersecting monotone CNF": conjunctive normal form, with each clause containing only positive or only negative terms, and each positive clause having a variable in common with each negative clause^[8]
Minimum circuit size problem: given the truth table of a Boolean function and positive integer $s$ , does there exist a circuit of size at most $s$ for this function?^[9]
Monotone dualization: given CNF and DNF formulas for monotone Boolean functions, do they represent the same function?^[10]
Monotone self-duality: given a CNF formula for a Boolean function, is the function invariant under a transformation that negates all of its variables and then negates the output value?^[10]

Computational geometry and computational topology

Determining whether the rotation distance^[11] between two binary trees or the flip distance between two triangulations of the same convex polygon is below a given threshold
The turnpike problem of reconstructing points on line from their distance multiset^[12]
The cutting stock problem with a constant number of object lengths^[13]
Knot triviality^[14]
Finding a simple closed quasigeodesic on a convex polyhedron^[15]

Game theory

Determining the winner in parity games, in which graph vertices are labeled by which player chooses the next step, and the winner is determined by the parity of the highest-priority vertex reached^[16]
Determining the winner for stochastic graph games, in which graph vertices are labeled by which player chooses the next step, or whether it is chosen randomly, and the winner is determined by reaching a designated sink vertex.^[17]

Graph algorithms

Graph isomorphism problem^[18]
Finding a graph's automorphism group^[19]
Finding the number of graph automorphisms^[19]
Planar minimum bisection^[20]
Deciding whether a graph admits a graceful labeling^[21]
Recognizing leaf powers and $k$ -leaf powers^[22]
Recognizing graphs of bounded clique-width^[23]
Testing the existence of a simultaneous embedding with fixed edges^[24]

Miscellaneous

Testing whether the Vapnik–Chervonenkis dimension of a given family of sets is below a given bound^[25]

References

^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM. 22 (1): 155–171. doi:10.1145/321864.321877. S2CID 14352974.
^ 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.
^ Kisfaludi-Bak, Sándor (2020). "Hyperbolic intersection graphs and (quasi)-polynomial time". In Chawla, Shuchi (ed.). Proceedings of the 31st Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. pp. 1621–1638. arXiv:1812.03960. doi:10.1137/1.9781611975994.100. ISBN 978-1-61197-599-4.
^ Eppstein, David; Lincoln, Andrea; Williams, Virginia Vassilevska (2023). "Quasipolynomiality of the smallest missing induced subgraph". Journal of Graph Algorithms and Applications. 27 (5): 329–339. arXiv:2306.11185. doi:10.7155/jgaa.00625.
^ Adleman, Leonard; Manders, Kenneth (1977). "Reducibility, randomness, and intractibility". Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77). doi:10.1145/800105.803405.
^ Papadimitriou, Christos H. (1994). Computational Complexity. Addison-Wesley. p. 236. ISBN 9780201530827.
^ Eiter, Thomas; Gottlob, Georg (2002). "Hypergraph transversal computation and related problems in logic and AI". In Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (eds.). Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings. Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564. doi:10.1007/3-540-45757-7_53.
^ 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. S2CID 785205. ECCC TR99-045.
^ ^a ^b Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "Computational aspects of monotone dualization: a brief survey". Discrete Applied Mathematics. 156 (11): 2035–2049. doi:10.1016/j.dam.2007.04.017. MR 2437000. S2CID 10096898.
^ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi:10.2307/1990951. JSTOR 1990951. MR 0928904.
^ Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstructing Sets from Interpoint Distances (Extended Abstract)". In Seidel, Raimund (ed.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990. ACM. pp. 332–339. doi:10.1145/98524.98598.
^ Jansen, Klaus; Solis-Oba, Roberto (2011). "A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths". Mathematics of Operations Research. 36 (4): 743–753. doi:10.1287/moor.1110.0515. MR 2855867.
^ Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm". Advances in Mathematics. 387: Paper No. 107796. arXiv:1604.00290. doi:10.1016/j.aim.2021.107796. MR 4274879. S2CID 119307517.
^ 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..
^ Jurdziński, Marcin (1998). "Deciding the winner in parity games is in UP $\cap$ co-UP". Information Processing Letters. 68 (3): 119–124. doi:10.1016/S0020-0190(98)00150-1. MR 1657581.
^ Condon, Anne (1992). "The complexity of stochastic games". Information and Computation. 96 (2): 203–224. doi:10.1016/0890-5401(92)90048-K. MR 1147987.
^ Grohe, Martin; Neuen, Daniel (June 2021). "Recent advances on the graph isomorphism problem". Surveys in Combinatorics 2021. Cambridge University Press. pp. 187–234. arXiv:2011.01366. doi:10.1017/9781009036214.006. S2CID 226237505.
^ ^a ^b Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8 (3): 131–132. doi:10.1016/0020-0190(79)90004-8.
^ Karpinski, Marek (2002). "Approximability of the minimum bisection problem: an algorithmic challenge". In Diks, Krzysztof; Rytter, Wojciech (eds.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings. Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67. doi:10.1007/3-540-45687-2_4.
^ Gallian, Joseph A. (December 17, 2021). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059.
^ 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 (PDF). Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335. doi:10.1007/11917496_29. MR 2290741..
^ 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

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.

[1] Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM. 22 (1): 155–171. doi:10.1145/321864.321877. S2CID 14352974.

[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] Kisfaludi-Bak, Sándor (2020). "Hyperbolic intersection graphs and (quasi)-polynomial time". In Chawla, Shuchi (ed.). Proceedings of the 31st Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. pp. 1621–1638. arXiv:1812.03960. doi:10.1137/1.9781611975994.100. ISBN 978-1-61197-599-4.

[5] Eppstein, David; Lincoln, Andrea; Williams, Virginia Vassilevska (2023). "Quasipolynomiality of the smallest missing induced subgraph". Journal of Graph Algorithms and Applications. 27 (5): 329–339. arXiv:2306.11185. doi:10.7155/jgaa.00625.

[6] Adleman, Leonard; Manders, Kenneth (1977). "Reducibility, randomness, and intractibility". Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77). doi:10.1145/800105.803405.

[7] Papadimitriou, Christos H. (1994). Computational Complexity. Addison-Wesley. p. 236. ISBN 9780201530827.

[8] Eiter, Thomas; Gottlob, Georg (2002). "Hypergraph transversal computation and related problems in logic and AI". In Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (eds.). Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings. Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564. doi:10.1007/3-540-45757-7_53.

[9] 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. S2CID 785205. ECCC TR99-045.

[emg-10] Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "Computational aspects of monotone dualization: a brief survey". Discrete Applied Mathematics. 156 (11): 2035–2049. doi:10.1016/j.dam.2007.04.017. MR 2437000. S2CID 10096898.

[11] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi:10.2307/1990951. JSTOR 1990951. MR 0928904.

[12] Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstructing Sets from Interpoint Distances (Extended Abstract)". In Seidel, Raimund (ed.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990. ACM. pp. 332–339. doi:10.1145/98524.98598.

[13] Jansen, Klaus; Solis-Oba, Roberto (2011). "A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths". Mathematics of Operations Research. 36 (4): 743–753. doi:10.1287/moor.1110.0515. MR 2855867.

[14] Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm". Advances in Mathematics. 387: Paper No. 107796. arXiv:1604.00290. doi:10.1016/j.aim.2021.107796. MR 4274879. S2CID 119307517.

[15] 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..

[16] Jurdziński, Marcin (1998). "Deciding the winner in parity games is in UP $\cap$ co-UP". Information Processing Letters. 68 (3): 119–124. doi:10.1016/S0020-0190(98)00150-1. MR 1657581.

[17] Condon, Anne (1992). "The complexity of stochastic games". Information and Computation. 96 (2): 203–224. doi:10.1016/0890-5401(92)90048-K. MR 1147987.

[18] Grohe, Martin; Neuen, Daniel (June 2021). "Recent advances on the graph isomorphism problem". Surveys in Combinatorics 2021. Cambridge University Press. pp. 187–234. arXiv:2011.01366. doi:10.1017/9781009036214.006. S2CID 226237505.

[mathon-19] Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8 (3): 131–132. doi:10.1016/0020-0190(79)90004-8.

[20] Karpinski, Marek (2002). "Approximability of the minimum bisection problem: an algorithmic challenge". In Diks, Krzysztof; Rytter, Wojciech (eds.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings. Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67. doi:10.1007/3-540-45687-2_4.

[21] Gallian, Joseph A. (December 17, 2021). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059.

[22] 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..

[23] 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..

[24] 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 (PDF). Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335. doi:10.1007/11917496_29. MR 2290741..

[25] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]