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.

  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.