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.

• 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}$

• 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]

• 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]

• 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]

• 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]

• 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]

• 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 .