En complejidad computacional , los problemas que están en la clase de complejidad NP pero que no están en la clase P ni NP-completo se denominan NP-intermedio , y la clase de tales problemas se llama NPI . El teorema de Ladner , mostrado en 1975 por Richard E. Ladner , [1] es un resultado que afirma que, si P ≠ NP , entonces NPI no está vacío; es decir, NP contiene problemas que no están ni en P ni en NP-completo. Dado que también es cierto que si existen problemas de NPI, entonces P ≠ NP, se deduce que P = NP si y solo si NPI está vacío.
Bajo el supuesto de que P ≠ NP, Ladner construye explícitamente un problema en NPI, aunque este problema es artificial y por lo demás poco interesante. Es una cuestión abierta si algún problema "natural" tiene la misma propiedad: el teorema de dicotomía de Schaefer proporciona condiciones bajo las cuales las clases de problemas de satisfacibilidad booleanos restringidos no pueden estar en NPI. [2] [3] Algunos problemas que se consideran buenos candidatos para ser NP-intermedio son el problema del isomorfismo gráfico , la factorización y el cálculo del logaritmo discreto . [4]
Lista de problemas que pueden ser NP intermedios [4]
Álgebra y teoría de números
- Factorizar enteros
- Problema de registro discreto y otros relacionados con supuestos criptográficos
- Problemas de isomorfismo: problema de isomorfismo de grupo , automorfismo de grupo , isomorfismo de anillo , automorfismo de anillo
- Problemas de números en cajas [5]
- El problema de la divisibilidad lineal [6]
lógica booleana
- Intersección Monotone SAT [7]
- Problema de tamaño mínimo del circuito [8] [9]
- Auto-dualidad monótona [10]
Geometría computacional y topología computacional
- Calcular la distancia de rotación [11] entre dos árboles binarios o la distancia de giro entre dos triangulaciones del mismo polígono convexo
- El problema de la autopista de peaje [12] de reconstruir puntos en línea a partir de su distancia multiset
- El problema del material de corte con un número constante de longitudes de objeto [13]
- Trivialidad del nudo [14]
- Decidir si una variedad tridimensional triangulada dada es una esfera tridimensional
- Versión de brecha del vector más cercano en el problema de celosía [15]
- Encontrar un cuasigeodésico cerrado simple en un poliedro convexo [16]
Teoría de juego
- Determinación del ganador en juegos de paridad [17]
- Determinar quién tiene la mayor probabilidad de ganar un juego estocástico [17]
- Control de agenda para torneos equilibrados de eliminación simple [18]
Algoritmos de grafos
- Problema de isomorfismo gráfico
- Bisección mínima plana [19]
- Decidir si un gráfico admite un etiquetado elegante [20]
- Reconociendo poderes de hojas y k poderes -leaf [21]
- Reconocimiento de gráficos de ancho de camarilla acotado [22]
- Encontrar una incrustación simultánea con bordes fijos [23]
Diverso
- Suponiendo que NEXP no es igual a EXP , versiones rellenadas de problemas completos de NEXP
- Problemas en TFNP [24]
- Suma del subconjunto de casilleros [25]
- Encontrar la dimensión VC [26]
Referencias
- ^ Ladner, Richard (1975). "Sobre la estructura de la reducibilidad del tiempo polinomial". Revista de la 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). Teoría de modelos finitos y sus aplicaciones . Textos en Informática Teórica. Una serie EATCS. Berlín: Springer-Verlag . pag. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001 .
- ^ Schaefer, Thomas J. (1978). "La complejidad de los problemas de satisfacibilidad" (PDF) . Proc. 10th Ann. ACM Symp. en Teoría de la Computación . págs. 216–226. Señor 0521057 .
- ^ a b "Problemas entre P y NPC" . Intercambio de pilas de informática teórica. 20 de agosto de 2011 . Consultado el 1 de noviembre de 2013 .
- ^ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
- ^ https://cstheory.stackexchange.com/q/4331
- ^ https://cstheory.stackexchange.com/q/1739
- ^ https://cstheory.stackexchange.com/q/1745
- ^ Kabanets, Valentine; Cai, Jin-Yi (2000), "Problema de minimización de circuitos", Proc. 32º Simposio sobre Teoría de la Computación , Portland, Oregón, EE. UU., Págs. 73–79, doi : 10.1145 / 335305.335314 , S2CID 785205 , ECCC TR99-045
- ^ https://cstheory.stackexchange.com/q/3950
- ^ Distancia de rotación, triangulaciones y geometría hiperbólica
- ^ Reconstrucción de conjuntos a partir de distancias entre puntos
- ^ 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", Algoritmos de plegado geométrico: enlaces, origami, poliedros , Cambridge: Cambridge University Press, págs. 372–375, doi : 10.1017 / CBO9780511735172 , ISBN 978-0-521-71522-5, Señor 2354878.
- ^ a b http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
- ^ https://cstheory.stackexchange.com/q/460
- ^ Aproximación del problema de bisección mínima: un desafío algorítmico
- ^ https://cstheory.stackexchange.com/q/6384
- ^ Nishimura, N .; Ragde, P .; Thilikos, DM (2002), "Sobre potencias gráficas para árboles etiquetados con hojas", Journal of Algorithms , 42 : 69–108, doi : 10.1006 / jagm.2001.1195.
- ^ Becarios, 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), "Embeddings simultáneos de gráficos con bordes fijos", Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Noruega, 22-24 de junio de 2006, Revised Papers (PDF) , Lecture Notes en Ciencias de la Computación, 4271 , Berlín: Springer, págs. 325–335, doi : 10.1007 / 11917496_29 , MR 2290741.
- ^ Sobre funciones totales, teoremas de existencia y complejidad computacional
- ^ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
- ^ Papadimitriou, Christos H .; Yannakakis, Mihalis (1996), "Sobre el no determinismo limitado y la complejidad de la dimensión VC", Journal of Computer and System Sciences , 53 (2, parte 1): 161-170, doi : 10.1006 / jcss.1996.0058 , MR 1418886
enlaces externos
- Complejidad Zoo : Clase NPI
- Estructura básica, reducibilidad de Turing y dureza NP
- Lance Fortnow (24 de marzo de 2003). "Fundamentos de la complejidad, lección 16: teorema de Ladner" . Consultado el 1 de noviembre de 2013 .