NP-intermediate: Difference between revisions
Content deleted Content added
→Algebra and number theory: numbers in boxes too inadequately sourced to keep. Linear divisibility can be properly sourced; needs explanation |
→Boolean logic: clean up sourcing |
||
| Line 35: | Line 35: | ||
===Boolean logic=== |
===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<ref>{{cite conference |
|||
* Intersecting Monotone [[Boolean satisfiability problem|SAT]]<ref>https://cstheory.stackexchange.com/q/1739</ref> |
|||
| last1 = Eiter | first1 = Thomas |
|||
| ⚫ | |||
| last2 = Gottlob | first2 = Georg |
|||
| editor1-last = Flesca | editor1-first = Sergio |
|||
| editor2-last = Greco | editor2-first = Sergio |
|||
| editor3-last = Leone | editor3-first = Nicola |
|||
| editor4-last = Ianni | editor4-first = Giovambattista |
|||
| contribution = Hypergraph transversal computation and related problems in logic and AI |
|||
| doi = 10.1007/3-540-45757-7_53 |
|||
| pages = 549–564 |
|||
| publisher = Springer |
|||
| series = Lecture Notes in Computer Science |
|||
| title = Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings |
|||
| volume = 2424 |
|||
| year = 2002}}</ref> |
|||
| ⚫ | |||
| first1 =Valentine |
| first1 =Valentine |
||
| last1 =Kabanets |
| last1 =Kabanets |
||
| Line 50: | Line 64: | ||
| s2cid =785205 |
| s2cid =785205 |
||
}}</ref> |
}}</ref> |
||
* 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?<ref>{{cite journal |
|||
* Monotone self-duality<ref>https://cstheory.stackexchange.com/q/3950</ref> |
|||
| last1 = Eiter | first1 = Thomas |
|||
| last2 = Makino | first2 = Kazuhisa |
|||
| last3 = Gottlob | first3 = Georg |
|||
| doi = 10.1016/j.dam.2007.04.017 |
|||
| issue = 11 |
|||
| journal = Discrete Applied Mathematics |
|||
| mr = 2437000 |
|||
| pages = 2035–2049 |
|||
| title = Computational aspects of monotone dualization: a brief survey |
|||
| volume = 156 |
|||
| year = 2008}}</ref> |
|||
===Computational geometry and computational topology=== |
===Computational geometry and computational topology=== |
||
Revision as of 05:54, 15 June 2022
 |
 |
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, factoring, and computing the discrete logarithm.[4]
List of problems that might be NP-intermediate[4]
Algebra and number theory
- Factoring integers
- Discrete Log Problem and others related to cryptographic assumptions
- Isomorphism problems: Group isomorphism problem, Group automorphism, Ring isomorphism, Ring automorphism
- Linear divisibility: given integers and , does have a divisor congruent to 1 modulo ?[5][6]
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[7]
- Minimum Circuit Size Problem[8]
- 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?[9]
Computational geometry and computational topology
- Computing the rotation distance[10] between two binary trees or the flip distance between two triangulations of the same convex polygon
- The turnpike problem[11] of reconstructing points on line from their distance multiset
- The cutting stock problem with a constant number of object lengths[12]
- Knot triviality[13]
- Deciding whether a given triangulated 3-manifold is a 3-sphere
- Gap version of the closest vector in lattice problem[14]
- Finding a simple closed quasigeodesic on a convex polyhedron[15]
Game theory
- Determining winner in parity games[16]
- Determining who has the highest chance of winning a stochastic game[16]
- Agenda control for balanced single-elimination tournaments[17]
Graph algorithms
- Graph isomorphism problem
- Planar minimum bisection[18]
- Deciding whether a graph admits a graceful labeling[19]
- Recognizing leaf powers and k-leaf powers[20]
- Recognizing graphs of bounded clique-width[21]
- Finding a simultaneous embedding with fixed edges[22]
Miscellaneous
- Assuming NEXP is not equal to EXP, padded versions of NEXP-complete problems
- Problems in TFNP[23]
- Pigeonhole subset sum[24]
- Finding the VC dimension[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.
- ^ a b "Problems Between P and NPC". Theoretical Computer Science Stack Exchange. 20 August 2011. Retrieved 1 November 2013.
- ^ 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.
- ^ 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.
- ^ Rotation distance, triangulations, and hyperbolic geometry
- ^ Reconstructing sets from interpoint distances
- ^ https://cstheory.stackexchange.com/q/3827
- ^ https://cstheory.stackexchange.com/q/1106
- ^ https://cstheory.stackexchange.com/q/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 "NP intersect coNP". 7 June 2010.
- ^ https://cstheory.stackexchange.com/q/460
- ^ Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
- ^ https://cstheory.stackexchange.com/q/6384
- ^ 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.
- ^ On total functions, existence theorems and computational complexity
- ^ "Subset-sums equality (Pigeonhole version) | Open Problem Garden".
- ^ 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.