NP-intermedio

En complejidad computacional , los problemas que pertenecen a la clase de complejidad NP pero que no pertenecen ni a la clase P ni son NP-completos se denominan NP-intermedios , y la clase de dichos problemas se denomina NPI . El teorema de Ladner , demostrado en 1975 por Richard E. Ladner , ^{[ 1 ]} es un resultado que afirma que, si P ≠ NP , entonces NPI no es vacío; es decir, NP contiene problemas que no pertenecen ni a 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 es 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 booleana con restricciones 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 cuasipolinomial y pueden resolverse en ese tiempo, incluyendo encontrar un conjunto grande y disjunto de discos unitarios a partir de un conjunto dado de discos en el plano hiperbólico [ ⁴^] y encontrar un grafo con pocos vértices que no sea un subgrafo inducido de un grafo dado ^[⁵^] . La hipótesis del tiempo exponencial también implica que ningún problema de tiempo cuasipolinomial puede ser NP-completo, por lo que bajo esta suposición estos problemas deben ser NP-intermedios.

Lista de problemas que podrían ser NP-intermedios

Álgebra y teoría de números

Una versión de decisión de factorización de enteros : para entrada $n$ y $k$ , hace $n$ tener un factor en el intervalo $[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 $x$ y $y$ , hace $y$ tener un divisor congruente con 1 módulo $x$ ¿ ^{[ 6 ]}^{[ 7 ]}

lógica booleana

IMSAT, el problema de satisfacibilidad booleana para "CNF monótona intersecante": forma normal conjuntiva , donde cada cláusula contiene solo términos positivos o solo términos negativos, y cada cláusula positiva tiene una variable en común con cada cláusula negativa ^{[ 8 ].}
Problema del tamaño mínimo del circuito : dada la tabla de verdad de una función booleana y un entero positivo $s$ ¿Existe un circuito de tamaño como máximo? $s$ ¿Para esta función? ^{[ 9 ]}
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, ¿es la función 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 volteo entre dos triangulaciones del mismo polígono convexo está por debajo de un umbral dado.
El problema de la autopista de reconstruir puntos en una línea a partir de su multiconjunto de distancias ^{[ 12 ]}
El problema del corte de material con un número constante de longitudes de objeto ^{[ 13 ]}
Trivialidad del nudo ^{[ 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 grafo están etiquetados según qué jugador elige el siguiente paso, y el ganador se determina por la paridad del vértice de mayor prioridad alcanzado ^{[ 16 ].}
Determinación del ganador en juegos de grafos estocásticos, en los que los vértices del grafo están etiquetados según qué jugador elige el siguiente paso, o si se elige aleatoriamente, y el ganador se determina al alcanzar un vértice sumidero designado. ^{[ 17 ]}

Algoritmos de grafos

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

Misceláneas

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

Referencias

↑ Ladner, Richard (1975). "Sobre la estructura de la reducibilidad en tiempo polinomial" . 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). Teoría de modelos finitos y sus aplicaciones . Textos en Ciencias de la Computación Teórica. Una serie de 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). «Grafos de intersección hiperbólica y tiempo (cuasi)polinomial». En Chawla, Shuchi (ed.). Actas del 31.er Simposio Anual ACM-SIAM sobre Algoritmos Discretos, SODA 2020, Salt Lake City, UT, EE. UU., 5-8 de enero de 2020. pp . 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). "Cuasipolinomio del subgrafo inducido faltante más pequeño" . Journal of Graph Algorithms and Applications . 27 (5): 329– 339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .
↑ Adleman, Leonard; Manders, Kenneth (1977). "Reducibilidad, aleatoriedad e intratabilidad". 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ógicas en Inteligencia Artificial, Conferencia Europea, JELIA 2002, Cosenza, Italia, 23-26 de septiembre, Actas . Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564 . doi : 10.1007/3-540-45757-7_53 . ISBN 978-3-540-44190-8.
↑ Kabanets, Valentine; Cai, Jin-Yi (2000). "Problema de minimización de circuitos". Actas del 32.º Simposio sobre Teoría de la Computación . Portland, Oregón, EE. UU. pp. 73–79 . doi : 10.1145/335305.335314 . ISBN 1-58113-184-4. S2CID 785205 . ECCC TR99-045 .
1 2 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" . Journal of the American Mathematical Society . 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 extendido)". 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 . ISBN 0-89791-362-0.
↑ Jansen, Klaus; Solis-Oba, Roberto (2011). "Un algoritmo OPT + 1 de tiempo polinomial para el problema de corte de material con un número constante de longitudes de objeto". Mathematics of Operations Research . 36 (4): 743– 753. doi : 10.1287/moor.1110.0515 . MR 2855867 .
↑ Lackenby, Marc (2021). "La certificación eficiente de la noción de nudos y la norma de Thurston" . Advances in Mathematics . 387 107796: Artículo 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. pp. 372–375 . doi : 10.1017/CBO9780511735172 . ISBN 978-0-521-71522-5. MR 2354878 . .
↑ Jurdziński, Marcin (1998). "Decidir el ganador en juegos de paridad está en UP $\cap$ co-UP". Information Processing Letters . 68 (3): 119– 124. doi : 10.1016/S0020-0190(98)00150-1 . MR 1657581 .
↑ Condon, Anne (1992). "La complejidad de los juegos estocásticos" . Information and Computation . 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». Surveys in Combinatorics 2021. Cambridge University Press. págs. 187–234 . arXiv : 2011.01366 . doi : 10.1017/9781009036214.006 . ISBN 978-1-009-03621-4. S2CID 226237505 .
1 2 Mathon, R. (1979). "Una nota sobre el problema del 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.). Fundamentos matemáticos de la informática 2002, 27.º Simposio Internacional, MFCS 2002, Varsovia, Polonia, 26-30 de agosto de 2002, Actas . Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67 . doi : 10.1007/3-540-45687-2_4 . ISBN 978-3-540-44040-6.
↑ Gallian, Joseph A. (17 de diciembre de 2021). "Una revisión dinámica del etiquetado de grafos" . Revista electrónica de combinatoria . 5 : Revisión dinámica 6. MR 1668059 .
↑ Nishimura, N.; Ragde, P.; Thilikos, DM (2002). "Sobre potencias de grafos para árboles con etiquetas de hojas". 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 clique es NP-completo". 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). "Incrustaciones simultáneas de grafos con aristas fijas". Conceptos de teoría de grafos en informática: 32.º Taller Internacional, WG 2006, Bergen, Noruega, 22-24 de junio de 2006, Artículos revisados (PDF) . Lecture Notes in Computer Science. Vol. 4271. Berlín: Springer. pp. 325–335 . doi : 10.1007/11917496_29 . ISBN 978-3-540-48381-6. MR 2290741 . Archivado del original (PDF) el 22-10-2021 . Recuperado el 10-09-2019 . .
↑ 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 complejidad : NPI de clase
Estructura básica, reducibilidad de Turing y NP-dureza
Lance Fortnow (24 de marzo de 2003). "Fundamentos de la complejidad, lección 16: el teorema de Ladner" . Consultado el 1 de noviembre de 2013 .

[1] Ladner, Richard (1975). "Sobre la estructura de la reducibilidad en tiempo polinomial" . Journal of the ACM . 22 (1): 155– 171. doi : 10.1145/321864.321877 . S2CID 14352974 .

[2] 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 Ciencias de la Computación Teórica. Una serie de EATCS. Berlín: Springer-Verlag . pág. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001 .

[3] 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 .

[4] Kisfaludi-Bak, Sándor (2020). «Grafos de intersección hiperbólica y tiempo (cuasi)polinomial». En Chawla, Shuchi (ed.). Actas del 31.er Simposio Anual ACM-SIAM sobre Algoritmos Discretos, SODA 2020, Salt Lake City, UT, EE. UU., 5-8 de enero de 2020. pp . 1621-1638 . arXiv : 1812.03960 . doi : 10.1137/1.9781611975994.100 . ISBN 978-1-61197-599-4.

[5] Eppstein, David ; Lincoln, Andrea; Williams, Virginia Vassilevska (2023). "Cuasipolinomio del subgrafo inducido faltante más pequeño" . Journal of Graph Algorithms and Applications . 27 (5): 329– 339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .

[6] Adleman, Leonard; Manders, Kenneth (1977). "Reducibilidad, aleatoriedad e intratabilidad". Actas del 9º Simposio ACM sobre Teoría de la Computación (STOC '77) . doi : 10.1145/800105.803405 .

[7] Papadimitriou, Christos H. (1994). Complejidad computacional . Addison-Wesley. pág. 236. ISBN 9780201530827.

[8] 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ógicas en Inteligencia Artificial, Conferencia Europea, JELIA 2002, Cosenza, Italia, 23-26 de septiembre, Actas . Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564 . doi : 10.1007/3-540-45757-7_53 . ISBN 978-3-540-44190-8.

[9] Kabanets, Valentine; Cai, Jin-Yi (2000). "Problema de minimización de circuitos". Actas del 32.º Simposio sobre Teoría de la Computación . Portland, Oregón, EE. UU. pp. 73–79 . doi : 10.1145/335305.335314 . ISBN 1-58113-184-4. S2CID 785205 . ECCC TR99-045 .

[emg-10] 1 2 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 .

[11] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Distancia de rotación, triangulaciones y geometría hiperbólica" . Journal of the American Mathematical Society . 1 (3): 647– 681. doi : 10.2307/1990951 . JSTOR 1990951. MR 0928904 .

[12] Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstrucción de conjuntos a partir de distancias entre puntos (Resumen extendido)". 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 . ISBN 0-89791-362-0.

[13] Jansen, Klaus; Solis-Oba, Roberto (2011). "Un algoritmo OPT + 1 de tiempo polinomial para el problema de corte de material con un número constante de longitudes de objeto". Mathematics of Operations Research . 36 (4): 743– 753. doi : 10.1287/moor.1110.0515 . MR 2855867 .

[14] Lackenby, Marc (2021). "La certificación eficiente de la noción de nudos y la norma de Thurston" . Advances in Mathematics . 387 107796: Artículo n.° 107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . MR 4274879. S2CID 119307517 .

[15] Demaine, Erik D.; O'Rourke , Joseph (2007). "24 Geodésicas: Lyusternik–Schnirelmann". Algoritmos de plegado geométrico: Enlaces, origami, poliedros . Cambridge: Cambridge University Press. pp. 372–375 . doi : 10.1017/CBO9780511735172 . ISBN 978-0-521-71522-5. MR 2354878 . .

[16] Jurdziński, Marcin (1998). "Decidir el ganador en juegos de paridad está en UP $\cap$ co-UP". Information Processing Letters . 68 (3): 119– 124. doi : 10.1016/S0020-0190(98)00150-1 . MR 1657581 .

[17] Condon, Anne (1992). "La complejidad de los juegos estocásticos" . Information and Computation . 96 (2): 203– 224. doi : 10.1016/0890-5401(92)90048-K . MR 1147987 .

[18] Grohe, Martin; Neuen, Daniel (junio de 2021). «Avances recientes en el problema del isomorfismo de grafos». Surveys in Combinatorics 2021. Cambridge University Press. págs. 187–234 . arXiv : 2011.01366 . doi : 10.1017/9781009036214.006 . ISBN 978-1-009-03621-4. S2CID 226237505 .

[mathon-19] 1 2 Mathon, R. (1979). "Una nota sobre el problema del conteo de isomorfismos de grafos". Information Processing Letters . 8 (3): 131– 132. doi : 10.1016/0020-0190(79)90004-8 .

[20] 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-30 de agosto de 2002, Actas . Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67 . doi : 10.1007/3-540-45687-2_4 . ISBN 978-3-540-44040-6.

[21] Gallian, Joseph A. (17 de diciembre de 2021). "Una revisión dinámica del etiquetado de grafos" . Revista electrónica de combinatoria . 5 : Revisión dinámica 6. MR 1668059 .

[22] Nishimura, N.; Ragde, P.; Thilikos, DM (2002). "Sobre potencias de grafos para árboles con etiquetas de hojas". Journal of Algorithms . 42 : 69–108 . doi : 10.1006/jagm.2001.1195 ..

[23] Fellows, Michael R. ; Rosamond, Frances A. ; Rotics, Udi; Szeider, Stefan (2009). "El ancho de clique es NP-completo". SIAM Journal on Discrete Mathematics . 23 (2): 909– 939. doi : 10.1137/070687256 . MR 2519936 . .

[24] Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). "Incrustaciones simultáneas de grafos con aristas fijas". Conceptos de teoría de grafos en informática: 32.º Taller Internacional, WG 2006, Bergen, Noruega, 22-24 de junio de 2006, Artículos revisados (PDF) . Lecture Notes in Computer Science. Vol. 4271. Berlín: Springer. pp. 325–335 . doi : 10.1007/11917496_29 . ISBN 978-3-540-48381-6. MR 2290741 . Archivado del original (PDF) el 22-10-2021 . Recuperado el 10-09-2019 . .

[25] 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 .

[ 1 ]

[ 2 ]

[ 3 ]

,

[

[ 6 ]

[ 7 ]

[ 8 ].

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ].

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]