NP-intermedio

En complejidad computacional , los problemas que están en la clase de complejidad NP pero no están en la clase P ni NP-completos se denominan NP-intermedios , y la clase de tales problemas se denomina 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 en P ni son NP-completos. Dado que también es cierto que si existen problemas 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 pregunta abierta si cualquier 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-intermedios son el problema de isomorfismo de grafos y las versiones de decisión de factorización y el logaritmo discreto .

Bajo la hipótesis del tiempo exponencial , existen problemas naturales que requieren un tiempo cuasi-polinomial , y pueden ser resueltos en ese tiempo, incluyendo encontrar un gran conjunto disjunto de discos unitarios a partir de un conjunto dado de discos en el plano hiperbólico , ^[4] y encontrar un grafo con pocos vértices que no sea un subgrafo inducido de un grafo dado. ^[5] La hipótesis del tiempo exponencial también implica que ningún problema de tiempo cuasi-polinomial puede ser NP-completo, por lo que bajo este supuesto estos problemas deben ser NP-intermedios.

Lista de problemas que pueden ser NP-intermedios

Álgebra y teoría de números

Una versión de decisión de factorización de números enteros : para la entrada y , ¿ tiene un factor en el intervalo ? ${\estilo de visualización n}$ ${\estilo de visualización k}$ ${\estilo de visualización n}$ ${\estilo de visualización [2,k]}$
Versiones de decisión del problema del logaritmo discreto y otras relacionadas con supuestos criptográficos
Divisibilidad lineal: dados los números enteros y , ¿ tiene un divisor congruente con 1 módulo ? ^[6]^[7] ${\estilo de visualización x}$ ${\estilo de visualización y}$ ${\estilo de visualización y}$ ${\estilo de visualización x}$

Lógica booleana

IMSAT, el problema de satisfacibilidad booleano para "CNF monótonas intersectantes": forma normal conjuntiva , en la que cada cláusula contiene solo términos positivos o solo negativos, y cada cláusula positiva tiene una variable en común con cada cláusula negativa ^[8]
Problema de tamaño mínimo del circuito : dada la tabla de verdad de una función booleana y un entero positivo , ¿existe un circuito de tamaño máximo para esta función? ^[9] ${\estilo de visualización s}$ ${\estilo de visualización s}$
Dualización monótona : dadas las fórmulas CNF y DNF para funciones booleanas monótonas, ¿representan la misma función? ^[10]
Autodualidad monótona: dada una fórmula CNF para una función booleana, ¿la función es invariante bajo una transformación que niega todas sus variables y luego niega el valor de salida? ^[10]

Geometría computacional y topología computacional

Determinar si la distancia de rotación ^[11] entre dos árboles binarios o la distancia de giro entre dos triangulaciones del mismo polígono convexo está por debajo de un umbral dado
El problema de la autopista de peaje de reconstruir puntos en línea a partir de su multiconjunto de distancias ^[12]
El problema del corte de material con un número constante de longitudes de objetos ^[13]
La trivialidad de los nudos ^[14]
Encontrar una cuasigeodésica cerrada simple en un poliedro convexo ^[15]

Teoría de juegos

Determinación del ganador en juegos de paridad , en los que los vértices del gráfico se etiquetan según el jugador que elige el siguiente paso, y el ganador se determina por la paridad del vértice de mayor prioridad alcanzado ^[16]
Determinar el ganador en juegos de gráficos estocásticos, en los que los vértices del gráfico se etiquetan según el jugador que elige el siguiente paso, o si se elige al azar y el ganador se determina al alcanzar un vértice sumidero designado. ^[17]

Algoritmos gráficos

Problema de isomorfismo de grafos ^[18]
Encontrar el grupo de automorfismos de un grafo ^[19]
Encontrar el número de automorfismos de grafos ^[19]
Bisección mínima planar ^[20]
Decidir si un gráfico admite un etiquetado elegante ^[21]
Reconocimiento de potencias de hojas y potencias de $k hojas$ ^[22]
Reconocimiento de gráficos de ancho de camarilla acotado ^[23]
Probando la existencia de una incrustación simultánea con bordes fijos ^[24]

Misceláneas

Comprobación de si la dimensión de Vapnik-Chervonenkis de una familia dada de conjuntos está por debajo de un límite dado ^[25]

Referencias

^ Ladner, Richard (1975). "Sobre la estructura de la reducibilidad temporal polinómica". 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 . pág. 348. ISBN. 978-3-540-00428-8.Zbl 1133.03001 .
^ Schaefer, Thomas J. (1978). "La complejidad de los problemas de satisfacibilidad" (PDF) . Actas del 10.º Simposio Anual de la ACM sobre Teoría de la Computación . págs. 216-226. MR 0521057.
^ Kisfaludi-Bak, Sándor (2020). "Gráficos de intersección hiperbólica y tiempo (cuasi)polinomial". En Chawla, Shuchi (ed.). Actas del 31.º Simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2020, Salt Lake City, UT, EE. UU., 5 al 8 de enero de 2020. págs. 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). "Cuasipolinomia del subgrafo inducido faltante más pequeño". Revista de algoritmos y aplicaciones de grafos . 27 (5): 329–339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .
^ Adleman, Leonard; Manders, Kenneth (1977). "Reducibilidad, aleatoriedad e intractibilidad". Actas del 9º Simposio ACM sobre teoría de la computación (STOC '77) . doi :10.1145/800105.803405.
^ Papadimitriou, Christos H. (1994). Complejidad computacional . Addison-Wesley. pág. 236. ISBN 9780201530827.
^ Eiter, Thomas; Gottlob, Georg (2002). "Cálculo transversal de hipergrafos y problemas relacionados en lógica e IA". En Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (eds.). Lógica en inteligencia artificial, Conferencia europea, JELIA 2002, Cosenza, Italia, septiembre, 23-26, Actas . Apuntes de clase en informática. Vol. 2424. Springer. págs. 549–564. doi :10.1007/3-540-45757-7_53.
^ 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.
^ ab Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "Aspectos computacionales de la dualización monótona: una breve revisión". Matemáticas Aplicadas Discretas . 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). "Distancia de rotación, triangulaciones y geometría hiperbólica". Revista de la Sociedad Americana de Matemáticas . 1 (3): 647–681. doi : 10.2307/1990951 . JSTOR 1990951. MR 0928904.
^ Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstrucción de conjuntos a partir de distancias entre puntos (resumen ampliado)". En Seidel, Raimund (ed.). Actas del Sexto Simposio Anual sobre Geometría Computacional, Berkeley, CA, EE. UU., 6-8 de junio de 1990. ACM. págs. 332–339. doi : 10.1145/98524.98598 .
^ Jansen, Klaus; Solis-Oba, Roberto (2011). "Un algoritmo de tiempo polinomial OPT + 1 para el problema de corte de material con un número constante de longitudes de objetos". Matemáticas de la investigación de operaciones . 36 (4): 743–753. doi :10.1287/moor.1110.0515. MR 2855867.
^ Lackenby, Marc (2021). "La certificación eficiente de la anudamiento y la norma de Thurston". Avances en Matemáticas . 387 : Documento n.º 107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . MR 4274879. S2CID 119307517.
^ Demaine, Erik D .; O'Rourke, Joseph (2007). "24 Geodésicas: 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 ..
^ Jurdziński, Marcin (1998). "Decidir quién es el ganador en los juegos de paridad está en UP co-UP". Cartas de procesamiento de la información . 68 (3): 119–124. doi :10.1016/S0020-0190(98)00150-1. MR 1657581. $\cap$
^ Condon, Anne (1992). "La complejidad de los juegos estocásticos". Información y computación . 96 (2): 203–224. doi : 10.1016/0890-5401(92)90048-K . MR 1147987.
^ Grohe, Martin; Neuen, Daniel (junio de 2021). "Avances recientes en el problema del isomorfismo de grafos". Encuestas en combinatoria 2021. Cambridge University Press. págs. arXiv : 2011.01366 . doi :10.1017/9781009036214.006. S2CID 226237505.
^ ab Mathon, R. (1979). "Una nota sobre el problema de conteo de isomorfismos de grafos". Information Processing Letters . 8 (3): 131–132. doi :10.1016/0020-0190(79)90004-8.
^ Karpinski, Marek (2002). "Aproximabilidad del problema de bisección mínima: un desafío algorítmico". En Diks, Krzysztof; Rytter, Wojciech (eds.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Varsovia, Polonia, 26-30 de agosto de 2002, Actas . Apuntes de clase en informática. Vol. 2420. Springer. págs. 59–67. doi :10.1007/3-540-45687-2_4.
^ Gallian, Joseph A. (17 de diciembre de 2021). "Un estudio dinámico del etiquetado de gráficos". Revista electrónica de combinatoria . 5 : Estudio dinámico 6. MR 1668059.
^ Nishimura, N.; Ragde, P.; Thilikos, DM (2002). "Sobre potencias gráficas para árboles con hojas etiquetadas". Journal of Algorithms . 42 : 69–108. doi :10.1006/jagm.2001.1195..
^ Fellows, Michael R. ; Rosamond, Frances A. ; Rotics, Udi; Szeider, Stefan (2009). "El ancho de camarilla es NP-completo". Revista SIAM de Matemáticas Discretas . 23 (2): 909–939. doi :10.1137/070687256. MR 2519936..
^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). "Incorporaciones simultáneas de grafos con aristas fijas". Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Noruega, 22-24 de junio de 2006, Documentos revisados (PDF) . Apuntes de clase en informática. Vol. 4271. Berlín: Springer. págs. 325–335. doi :10.1007/11917496_29. MR 2290741..
^ 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

Zoológico de la complejidad : 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 .