NP-intermedio

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 llaman 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. Como también es cierto que si existen problemas de NPI, entonces P ≠ NP, se deduce que P = NP si y sólo 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 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 de isomorfismo gráfico y las versiones de decisión de factorización y logaritmo discreto .

Lista de problemas que podrían ser NP-intermedio

Álgebra y teoría de números.

Una versión de decisión de factorizar números enteros : para entrada y , ¿ tiene un factor en el intervalo ? $n$ $k$ $n$ $[2,k]$
Versiones de decisión del problema del logaritmo discreto y otros relacionados con supuestos criptográficos
Divisibilidad lineal: dados los números enteros y , ¿ tiene un divisor congruente con 1 módulo ? ^[4]^[5] $x$ $y$ $y$ $x$

lógica booleana

IMSAT, el problema booleano de satisfacibilidad para "CNF monótono que se cruza": forma normal conjuntiva , en la que cada cláusula contiene sólo términos positivos o sólo negativos, y cada cláusula positiva tiene una variable en común con cada cláusula negativa ^[6]
Problema de tamaño mínimo de 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? ^[7] $s$ $s$
Dualización monótona : dadas las fórmulas CNF y DNF para funciones booleanas monótonas, ¿representan la misma función? ^[8]
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? ^[8]

Geometría computacional y topología computacional.

Determinar si la distancia de rotación ^[9] entre dos árboles binarios o la distancia de giro entre dos triangulaciones del mismo polígono convexo está por debajo de un umbral determinado
El problema de la autopista de peaje de reconstruir puntos en línea a partir de su conjunto de distancias ^[10]
El problema del material de corte con un número constante de longitudes de objeto ^[11]
Trivialidad del nudo ^[12]
Encontrar una cuasigeodésica cerrada simple en un poliedro convexo ^[13]

Teoría de juego

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

Algoritmos gráficos

Problema de isomorfismo gráfico ^[16]
Bisección mínima plana ^[17]
Decidir si un gráfico admite un etiquetado elegante ^[18]
Reconocer los poderes de las hojas y los poderes de las hojas $k$ ^[19]
Reconocimiento de gráficos de ancho de camarilla acotado ^[20]
Probando la existencia de una incrustación simultánea con bordes fijos ^[21]

Misceláneas

Probar si la dimensión de Vapnik-Chervonenkis de una determinada familia de conjuntos está por debajo de un límite determinado ^[22]

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; Kolaítis, Phokion G.; Libkin, Leonid; Marx, Martín; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos de 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. Décimo ann. Síntoma ACM. sobre Teoría de la Computación . págs. 216–226. SEÑOR 0521057.
^ Adleman, Leonard; Manders, Kenneth (1977). "Reducibilidad, aleatoriedad e intratibilidad". 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. pag. 236.ISBN 9780201530827.
^ Eiter, Thomas; Gottlob, Georg (2002). "Computación transversal de hipergrafo y problemas relacionados en lógica e inteligencia artificial". En Flesca, Sergio; Greco, Sergio; Leona, Nicola; Ianni, Giovambattista (eds.). Logics in Artificial Intelligence, Conferencia europea, JELIA 2002, Cosenza, Italia, 23-26 de septiembre, Actas . Apuntes de conferencias sobre informática. vol. 2424. Saltador. págs. 549–564. doi :10.1007/3-540-45757-7_53.
^ Kabanets, San Valentín; Cai, Jin-Yi (2000). "Problema de minimización de circuitos". Proc. 32º Simposio de Teoría de la Computación . Portland, Oregón, Estados Unidos. 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: un breve estudio". Matemática Aplicada Discreta . 156 (11): 2035-2049. doi : 10.1016/j.dam.2007.04.017 . SEÑOR 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 Matemática Estadounidense . 1 (3): 647–681. doi : 10.2307/1990951 . JSTOR 1990951. SEÑOR 0928904.
^ Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstrucción de conjuntos a partir de distancias de interpunto (resumen ampliado)". En Seidel, Raimund (ed.). Actas del Sexto Simposio Anual sobre Geometría Computacional, Berkeley, CA, EE. UU., 6 al 8 de junio de 1990 . ACM. págs. 332–339. doi : 10.1145/98524.98598 .
^ Jansen, Klaus; Solís-Oba, Roberto (2011). "Un algoritmo de tiempo polinómico OPT + 1 para el problema del material de corte con un número constante de longitudes de objeto". Matemáticas de la Investigación de Operaciones . 36 (4): 743–753. doi :10.1287/moor.1110.0515. SEÑOR 2855867.
^ Lackenby, Marc (2021). "La certificación eficiente de anudado y norma Thurston". Avances en Matemáticas . 387 : Documento nº 107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . SEÑOR 4274879. S2CID 119307517.
^ Demaine, Erik D .; O'Rourke, Joseph (2007). "24 geodésicas: Lyusternik-Schnirelmann". Algoritmos de plegado geométrico: Vínculos, origami, poliedros . Cambridge: Prensa de la Universidad de Cambridge. págs. 372–375. doi :10.1017/CBO9780511735172. ISBN 978-0-521-71522-5. SEÑOR 2354878..
^ Jurdziński, Marcin (1998). "Decidir el ganador en los juegos de paridad es en UP co-UP". Cartas de procesamiento de información . 68 (3): 119-124. doi :10.1016/S0020-0190(98)00150-1. SEÑOR 1657581. ${\displaystyle\cap}$
^ Condón, 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 . SEÑOR 1147987.
^ Grohe, Martín; Neuen, Daniel (junio de 2021). "Avances recientes en el problema del isomorfismo gráfico". Encuestas en Combinatoria 2021 . Prensa de la Universidad de Cambridge. págs. 187-234. arXiv : 2011.01366 . doi :10.1017/9781009036214.006. S2CID 226237505.
^ Karpinski, Marek (2002). "Aproximabilidad del problema de bisección mínima: un desafío algorítmico". En Diks, Krzysztof; Rytter, Wojciech (eds.). Fundamentos matemáticos de la informática 2002, 27º Simposio internacional, MFCS 2002, Varsovia, Polonia, 26 al 30 de agosto de 2002, Actas . Apuntes de conferencias sobre informática. vol. 2420. Saltador. 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 : Encuesta dinámica 6. SEÑOR 1668059.
^ Nishimura, N.; Ragde, P.; Thilikos, DM (2002). "Sobre potencias gráficas para árboles etiquetados con hojas". Revista de algoritmos . 42 : 69-108. doi :10.1006/jagm.2001.1195..
^ Becarios, Michael R .; Rosamond, Frances A .; Róticos, Udi; Szeider, Stefan (2009). "El ancho de camarilla es NP completo". Revista SIAM de Matemática Discreta . 23 (2): 909–939. doi : 10.1137/070687256. SEÑOR 2519936..
^ Gassner, Isabel; Jünger, Michael; Percán, Merijam; Schaefer, Marcos; Schulz, Michael (2006). "Incrustaciones de gráficos simultáneos con bordes fijos". Conceptos de teoría de grafos en informática: 32º taller internacional, WG 2006, Bergen, Noruega, 22 al 24 de junio de 2006, artículos revisados (PDF) . Apuntes de conferencias sobre informática. vol. 4271. Berlín: Springer. págs. 325–335. doi :10.1007/11917496_29. SEÑOR 2290741..
^ Papadimitriou, Christos H .; Yannakakis, Mihalis (1996). "Sobre el no determinismo limitado y la complejidad de la dimensión VC". Revista de Ciencias de la Computación y de Sistemas . 53 (2, parte 1): 161–170. doi : 10.1006/jcss.1996.0058 . SEÑOR 1418886.

enlaces externos

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