¿Hay problemas de NP, no en P ni en NP Complete?

34

¿Hay algún problema conocido en NP (y no en P ) que no sea NP Complete? Tengo entendido que actualmente no hay problemas conocidos en este caso, pero no se ha descartado como una posibilidad.

Si hay un problema que es NP (y no P ) pero no NP-complete , ¿sería esto el resultado de un isomorfismo no existente entre las instancias de ese problema y el NP-complete set? En este caso, ¿cómo podríamos saber que el problema NP no es "más difícil" de lo que actualmente identificamos como NP-complete set?

vpiTriumph
fuente
1
Ver también esta pregunta relacionada .
Raphael

Respuestas:

25

¿Hay algún problema conocido en NP (y no en P) que no sea NP completo? Tengo entendido que actualmente no hay problemas conocidos en este caso, pero no se ha descartado como una posibilidad.

No, esto es desconocido (con la excepción de los lenguajes triviales y Σ , estos dos no están completos debido a la definición de reducciones de muchos, generalmente estos dos se ignoran al considerar las reducciones de muchos). La existencia de un problema de N P que no está completo para N P wrt muchas reducciones de tiempo polinomiales implicaría que PN P que no se conoce (aunque se cree ampliamente). Si las dos clases son diferentes entonces sabemos que hay problemas en N P que no se completa para que, toman ningún problema en P .ΣNPNPPNPNPP

Si hay un problema que es NP (y no P) pero no NP completo, ¿sería esto el resultado de un isomorfismo existente entre las instancias de ese problema y el conjunto NP completo?

Si las dos clases de complejidad son diferentes, entonces, según el teorema de Ladner, hay problemas que son intermedios, es decir, están entre P y N P - c o m p l e t e .NPPNP-complete

En este caso, ¿cómo podríamos saber que el problema NP no es "más difícil" de lo que actualmente identificamos como el conjunto NP completo?

Siguen siendo reducible tiempo polinómico a problemas por lo que no puede ser más difícil de N P - c o m p l e t e problemas.NP-completeNP-complete

Kaveh
fuente
Han pasado algunos años, pero tenía la impresión de que los problemas de NP-Hard se ajustan a la descripción del OP, ¿dónde encajan?
Kevin
2
@Kevin: No, NP-hard significa que un problema es al menos tan difícil como los problemas más difíciles en NP.
Huck Bennett
¿Qué pasa con los problemas con el tiempo de ejecución psuedo-polinomial?
Joe
@ Joe, no estoy seguro de lo que quieres decir, si tienes una pregunta, publícala como una nueva pregunta.
Kaveh
1
Oh, por supuesto, suponiendo P! = NP. Tal problema sería el isomorfismo gráfico, ¿verdad?
levi
11

Como dijo @Kaveh, esta pregunta solo es interesante si suponemos ; El resto de mi respuesta toma esto como una suposición, y en su mayoría proporciona enlaces para humedecer aún más su apetito. Bajo ese supuesto, por el teorema de Ladner sabemos que hay problemas que no están ni en P ni en N P C ; estos problemas se llaman N P intermedio: o N P I . Curiosamente, el teorema de Ladner se puede generalizar a muchas otras clases de complejidad para producir problemas intermedios similares. Además, el teorema también implica que hay una jerarquía infinita.PNPPNPCNPNPIde los problemas intermedios que no son en tiempo poli reducible entre sí en .NPI

Desafortunadamente, incluso con la suposición es muy difícil encontrar problemas naturales que pudieran ser probables N P I (por supuesto, usted tiene los problemas artificiales que provienen de la demostración del teorema de Ladner). Por lo tanto, incluso suponiendo que P N P en este momento solo podemos creer que algunos problemas son N P I pero no lo demostramos. Llegamos a tales creencias cuando tenemos evidencia razonable para creer que un problema de N P no está en N P C y / o no está en PPNPNPIPNPNPINPNPCP; o solo cuando se ha estudiado durante mucho tiempo y se ha evitado encajar en cualquiera de las clases. Hay una lista bastante completa de tales problemas en esta respuesta . Incluye favoritos de todos los tiempos como factorización, registro discreto e isomorfismo gráfico.

BQPBQPN P I B Q PNPCBQPNPIBQP

Artem Kaznatcheev
fuente
Un resultado realmente reciente de Babai (ver jeremykun.com/2015/11/12/… ) da un algoritmo cuasipolinomial para el isomorfismo gráfico, básicamente eliminándolo de NPI, si el resultado es válido. Curiosamente, era el problema que no se sabía que estaba en BQP
Frédéric Grosshans
1
@ FrédéricGrosshans que tiene un algoritmo de tiempo cuasipolinomial no lo elimina de NPI (de hecho, ni siquiera lo eliminaría de NPC a menos que haga suposiciones más fuertes que solo P! = NP). El resultado de Babai (si es correcto, lo que probablemente sea) solo proporciona evidencia circunstancial de que GraphIso podría estar en P, porque en el pasado cuando se encontraron algoritmos cuasipolinomiales para problemas difíciles, eventualmente condujeron a algoritmos polinomiales.
Artem Kaznatcheev
1
@ FrédéricGrosshans Babai se retractó del reclamo de tiempo de ejecución cuasipolinomial . Aparentemente hubo un error en el análisis.
Raphael
@Raphael, según mi comentario anterior, no creo que Babai relaje el cuasipolinomio a subexponencial no es particularmente relevante para la discusión en cuestión.
Artem Kaznatcheev
Dado que ese comentario todavía está aquí, no quería que quedara sin corregir. (Básicamente, rastreé todas las ocurrencias de "Babai" en el sitio y publiqué el mismo comentario). Siéntase libre de marcar todos los comentarios para sentir que son obsoletos como tales.
Raphael
7

No NP problemas -Complete son conocidos por ser en P . Si hay un algoritmo de tiempo polinomial para cualquier problema NP completo, entonces P = NP , porque cualquier problema en NP tiene una reducción de tiempo polinomial para cada problema NP completo. (Así es como se define " NP- completo"). Y obviamente, si cada problema de NP- completo se encuentra fuera de P , esto significa que PNP . No estamos realmente seguros de por qué es difícil mostrarlo de una forma u otra; Si supiéramos la respuesta a esa pregunta, probablemente sabríamos mucho más sobre P yNP . Tenemos algunas técnicas de prueba que sabemos que no funcionan (relativización y pruebas naturales, por ejemplo), pero no tenemos una explicación basada en principios de por qué este problema es difícil.

Si hay problemas en NP que no están en P , entonces en realidad hay una jerarquía infinita de problemas en NP entre aquellos en P y aquellos que están completos en NP : este es un resultado llamado teorema de Ladner .

¡Espero que esto ayude!

templatetypedef
fuente
explique: ¿No se sabe que los problemas en NP no están en P? ¿No están todas las P ya en NP?
1
@ Shimano: estos son dos conceptos diferentes: se sabe que todos los problemas en P están en NP. Sin embargo, no sabemos si algún problema en NP no está en P. Es decir, sabemos que P es un subconjunto de NP, pero no sabemos si NP es un subconjunto de P. ¿Eso aclara las cosas?
templatetypedef
Las cosas se están aclarando ahora. Muchas gracias por sus respuestas rápidas. Se necesita una aclaración más. Usted dijo: "La razón de esto es que cualquier problema en NP tiene una reducción de tiempo polinomial para cada problema de NP completo". Esto demuestra que todos los problemas en NP son NP-complete automáticamente? Estoy un poco confundido de nuevo
@ Shimano- No del todo. La dirección de la reducción es importante. Un problema es NP completo si todos los problemas en NP se reducen a ese problema. También puede mostrar que un problema es NP-hard reduciendo un problema NP-complete conocido a ese problema. Sin embargo, mostrar que un problema en NP se reduce a un problema NP-completo conocido no muestra nada nuevo, ya que, por definición, todos los problemas NP se reducen a todos los problemas NP-completos.
templatetypedef
1
@ El teorema de Shimano-Ladner dice que si P! = NP, entonces debe haber problemas NP-intermedios, por lo que si no hay problemas NP-intermedios, entonces P = NP. Y sí, si podemos encontrar un problema en NP que no esté en P, independientemente de si está en BQP, entonces P! = NP.
templatetypedef