Lista de teoremas que indican que P no es igual a NP si y solo si

18

Creo que sería una buena idea hacer una lista de teoremas que indiquen que P no es igual a NP si y solo si tales y tales salidas, alguna clase de complejidad está contenida en otra clase de complejidad y así sucesivamente.

cc.complexity-theory big-list p-vs-np Tayfun Pay
fuente
15
¡Eso sería una fracción constante de todos los documentos de complejidad!
MCH
55
Yo diría: "lista de condiciones que implican P? NP", ya que no todos esos teoremas son "si y solo si". Además, supongo que la gente está más interesada, en general, en saber cómo probar P? NP demostrando algo más que en enumerar las muchas consecuencias de este resultado, un tema que se ha discutido ampliamente en otros lugares.
Janoma
2
@Janoma: si quieres restringirte a las implicaciones, entonces la lista será realmente enorme, dada la enorme cantidad de resultados de la forma: "Si P! = NP, entonces el problema X no puede resolverse exactamente / aproximarse dentro de un factor constante en tiempo polinómico ". La pregunta debería estar mucho más centrada o mejor formulada si queremos evitar eso.
Anthony Labarre
44
@ Janoma: Eso no resuelve la preocupación bien fundada de Anthony. Las hipótesis que implican P = NP son simplemente negaciones de las consecuencias de P ≠ NP, y las hipótesis que implican P ≠ NP son negaciones de las consecuencias de P = NP. Si SAT es solucionable en tiempo polinómico, entonces P = NP. Si Max3SAT es un tiempo polinómico aproximado dentro de un factor constante menor que 8/7, entonces P = NP. Y así.
Tsuyoshi Ito
77
@Janoma: "Si X entonces P = NP" es lo mismo que "Si P ≠ NP entonces no-X".
Jeffε

Respuestas:

11

Aquí hay uno:

Teorema de Mahaney: no hay un conjunto completo de NP escaso si y solo si (bajo reducción de Karp).P≠NP

Otro es:

si y solo si P ≠ P HP≠NPP≠PH

Mohammad Al-Turkistany
fuente
Puede ser esto es sencillo: si y sólo si F P ≠ F N P . P≠NPFP≠FNP
Mohammad Al-Turkistany
11

si y solo si existen las funciones unidireccionales en el peor de los casos.P≠NP

Referencia:

Alan L. Selman. Una encuesta de funciones unidireccionales en teoría de la complejidad. Teoría de sistemas matemáticos, 25 (3): 203–221, 1992.

Mohammad Al-Turkistany
fuente
1
una referencia sería buena
vzn
¿Estás seguro? Yo no había oído hablar de OWFs peor de los casos antes, pero a partir de las notas aquí parece que su existencia es equivalente a . siPAGPAG≠nortePAG
Huck Bennett
Sí, estoy seguro. :) Ver la referencia.
Mohammad Al-Turkistany
8

Aquí hay un resultado de la teoría de la complejidad descriptiva:

si y solo si alguna propiedad de segundo orden no es expresable usando la lógica de primer orden más el punto menos fijo.PAG≠nortePAG

Referencia: Immerman, Idiomas que capturan clases de complejidad.

Mohammad Al-Turkistany
fuente
... en estructuras ordenadas. De lo contrario, sabemos incondicionalmente que tales propiedades existen.
Emil Jeřábek apoya a Monica el
@ EmilJeřábek sí, en estructuras ordenadas, como lo asumió implícitamente Immerman en el documento anterior.
Mohammad Al-Turkistany
7

El teorema de Ladner se puede expresar como:

si y sólo si existe un conjunto incompleto en N P - P .PAG≠nortePAGnortePAG-PAG

El conjunto incompleto es un conjunto que no está completo para bajo varias reducciones de tiempo polinomiales.nortePAG

Referencia

Teoría de la complejidad y criptología: una introducción a la criptocomplejidad Por Jörg Rothe, página 106

Mohammad Al-Turkistany
fuente