NP-intermediate

NP-intermediate (Redirected from Ladner's theorem) Jump to navigation Jump to search 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; C'est, 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 "Naturel" 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.

Contenu 1 List of problems that might be NP-intermediate 1.1 Algebra and number theory 1.2 Boolean logic 1.3 Computational geometry and computational topology 1.4 Game theory 1.5 Graph algorithms 1.6 Miscellaneous 2 Références 3 External links List of problems that might be NP-intermediate 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 {style d'affichage x} et {style d'affichage y} , does {style d'affichage y} have a divisor congruent to 1 modulo {style d'affichage x} ?[4][5] 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[6] Minimum Circuit Size Problem[7] 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?[8] Computational geometry and computational topology Computing the rotation distance[9] between two binary trees or the flip distance between two triangulations of the same convex polygon The turnpike problem of reconstructing points on line from their distance multiset[10] The cutting stock problem with a constant number of object lengths[11] Knot triviality[12] Finding a simple closed quasigeodesic on a convex polyhedron[13] Game theory Determining 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[14] 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.[15] Graph algorithms Graph isomorphism problem[16] Planar minimum bisection[17] Deciding whether a graph admits a graceful labeling[18] Recognizing leaf powers and k-leaf powers[19] Recognizing graphs of bounded clique-width[20] Finding a simultaneous embedding with fixed edges[21] Miscellaneous Problems in TFNP[22] Pigeonhole subset sum: given {displaystyle n} positive integers whose sum is less than {style d'affichage 2 ^{n}-1} , find two distinct subsets with the same sum[23] Finding the Vapnik–Chervonenkis dimension of a given family of sets[24] References ^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal de l'ACM. 22 (1): 155–171. est ce que je:10.1145/321864.321877. S2CID 14352974. ^ Grädel, Érich; Kolaitis, Phokion G.; Libkin, Léonid; 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. ^ Schäfer, Thomas J. (1978). "La complexité des problèmes de satisfaisabilité" (PDF). Proc. 10th Ann. ACM Symp. on Theory of Computing. pp. 216–226. M 0521057. ^ Adleman, Léonard; Manders, Kenneth (1977). "Reducibility, randomness, and intractibility". Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77). est ce que je:10.1145/800105.803405. ^ Papadimitriou, Christos H. (1994). Complexité informatique. 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 (éd.). Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italie, Septembre, 23-26, Procédure. Notes de cours en informatique. Volume. 2424. Springer. pp. 549–564. est ce que je: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, Etats-Unis. pp. 73–79. est ce que je:10.1145/335305.335314. S2CID 785205. ECCC TR99-045. ^ Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "Computational aspects of monotone dualization: a brief survey". Mathématiques discrètes appliquées. 156 (11): 2035–2049. est ce que je:10.1016/j.dam.2007.04.017. M 2437000. S2CID 10096898. ^ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal de l'American Mathematical Society. 1 (3): 647–681. est ce que je:10.2307/1990951. JSTOR 1990951. M 0928904. ^ Skiena, Steven; Forgeron, Warren D.; Lemke, Paul (1990). "Reconstructing Sets from Interpoint Distances (Extended Abstract)". In Seidel, Raimund (éd.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, Californie, Etats-Unis, Juin 6-8, 1990. ACM. pp. 332–339. est ce que je:10.1145/98524.98598. ^ Jansen, Klaus; Solis-Oba, Robert (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. est ce que je:10.1287/moor.1110.0515. M 2855867. ^ Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm". Avancées en mathématiques. 387: Paper No. 107796. arXiv:1604.00290. est ce que je:10.1016/j.aim.2021.107796. M 4274879. S2CID 119307517. ^ Demaine, Éric D.; O'Rourke, Joseph (2007). "24 Geodesics: Lyusternik–Schnirelmann". Geometric folding algorithms: Liens, origami, polyhedra. Cambridge: la presse de l'Universite de Cambridge. pp. 372–375. est ce que je:10.1017/CBO9780511735172. ISBN 978-0-521-71522-5. M 2354878.. ^ Jurdziński, Marcin (1998). "Deciding the winner in parity games is in UP {displaystyle cap } co-UP". Lettres de traitement de l'information. 68 (3): 119–124. est ce que je:10.1016/S0020-0190(98)00150-1. M 1657581. ^ Condon, Anne (1992). "The complexity of stochastic games". Information et calcul. 96 (2): 203–224. est ce que je:10.1016/0890-5401(92)90048-K. M 1147987. ^ Grohe, Martin; Neuen, Daniel (Juin 2021). "Recent advances on the graph isomorphism problem". Surveys in Combinatorics 2021. la presse de l'Universite de Cambridge. pp. 187–234. arXiv:2011.01366. est ce que je:10.1017/9781009036214.006. S2CID 226237505. ^ Karpinski, marek (2002). "Approximability of the minimum bisection problem: an algorithmic challenge". In Diks, Krzysztof; Rytter, Wojciech (éd.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Pologne, Août 26-30, 2002, Procédure. Notes de cours en informatique. Volume. 2420. Springer. pp. 59–67. est ce que je:10.1007/3-540-45687-2_4. ^ Gallian, Joseph A. (Décembre 17, 2021). "A dynamic survey of graph labeling". Journal électronique de combinatoire. 5: Dynamic Survey 6. M 1668059. ^ Nishimura, N; Ragde, P; Thilikos, D.M. (2002). "On graph powers for leaf-labeled trees". Journal des algorithmes. 42: 69–108. est ce que je:10.1006/jagm.2001.1195.. ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stéphane (2009). "Clique-width is NP-complete". SIAM Journal sur les mathématiques discrètes. 23 (2): 909–939. est ce que je:10.1137/070687256. M 2519936.. ^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schäfer, Marc; Schulz, Michael (2006). "Simultaneous graph embeddings with fixed edges". Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, Juin 22-24, 2006, Revised Papers (PDF). Notes de cours en informatique. Volume. 4271. Berlin: Springer. pp. 325–335. est ce que je:10.1007/11917496_29. M 2290741.. ^ Megiddo, Nimrod; Papadimitriou, Christos H. (1991). "On total functions, existence theorems and computational complexity" (PDF). Informatique théorique. 81 (2): 317–324. est ce que je:10.1016/0304-3975(91)90200-L. M 1107721. ^ Papadimitriou, Christos H. (1994). "On the complexity of the parity argument and other inefficient proofs of existence". Journal des sciences informatiques et des systèmes. 48 (3): 498–532. est ce que je:10.1016/S0022-0000(05)80063-7. M 1279412. ^ Papadimitriou, Christos H.; Yannakakis, Mihalis (1996). "On limited nondeterminism and the complexity of the V-C dimension". Journal des sciences informatiques et des systèmes. 53 (2, partie 1): 161–170. est ce que je:10.1006/jcss.1996.0058. M 1418886. External links Complexity Zoo: Class NPI Basic structure, Turing reducibility and NP-hardness Lance Fortnow (24 Mars 2003). "Fondements de la complexité, Leçon 16: Ladner's Theorem". Récupéré 1 Novembre 2013. Catégories: Complexity classes