Dureza de aproximación suponiendo NP! = CoNP

32

Dos de los supuestos comunes para probar la dureza de los resultados de aproximación son y Unique Games Conjecture. ¿Hay alguna dureza de los resultados de aproximación suponiendo N P c o N P ? Estoy buscando el problema A tal que "es difícil aproximar A dentro de un factor α a menos que N P = c o N P ".PNPNPcoNPAAαNP=coNP

Se sabe que "mostrar la dureza del factor NP para el problema del vector más corto implicaría que N P = c o N P ". Tenga en cuenta que este es el "opuesto" de lo que estoy buscando.nNP=coNP

Aclaración: es posible que y aún la pregunta P vs NP esté abierta. Estoy en busca de dureza de resultado aproximación que se convertirá en falso si N P = c o N P pero no se ve afectado (es decir, todavía permanece como una conjetura) por P N P .NP=coNPNP=coNPPNP

Shiva Kintali
fuente
@ Kintali, El resultado SVP es interesante. ¿Conoce otros ejemplos similares al resultado del problema de vector más corto?
Mohammad Al-Turkistany
No tengo conocimiento de más resultados de este tipo.
Shiva Kintali

Respuestas:

20

Aquí hay una observación directa. Si asume , entonces es bastante fácil ver que hay problemas de optimización de N P que ni siquiera tienen buenos algoritmos de aproximación no deterministas , en cierto sentido.NPcoNPNP

Por ejemplo, el teorema de PCP dice que puede traducir SAT en el problema de distinguir si de las cláusulas están satisfechas y todas las cláusulas están satisfechas, para algunos ε > 0 . Supongamos que hay un algoritmo no determinista que puede distinguir entre estos dos casos, en el sentido de que el algoritmo no determinista puede informar en cada ruta de cálculo "todos satisfechos" o "a lo sumo 1 - ε ", y dice "a lo sumo 1 - ε "en alguna ruta si como máximo 1 - ε1εε>01ε1ε1εpuede satisfacerse, de lo contrario dice "todos satisfechos" en cada ruta de cálculo si se pueden satisfacer todas las ecuaciones. Esto es suficiente para decidir SAT en , por lo que N P = c o N P . Parece claro que la existencia de un tal algoritmo no determinista no influye en si P = N P .coNPNP=coNPP=NP

Es bastante convincente que existe un escenario más "natural": un problema de optimización que es difícil de aproximado en determinista tiempo polinómico bajo pero no conocido por ser duro bajo P N P . (Esto es probablemente lo que realmente quería preguntar). Muchos resultados de dureza de aproximación se prueban primero bajo un supuesto más fuerte (por ejemplo, N P no en tiempo subexponencial, o N P no en B P P ). En algunos casos, las mejoras posteriores debilitan el supuesto necesario, a veces hasta P NNPcoNPPNPNPNPBPP . Por lo tanto, existe la esperanza de que haya una respuesta un poco más satisfactoria a su pregunta que esta. Es difícil de extrañar cómo podría ser un problema queno puedeser probado difícil de aproximar en polytime determinista bajo P N P , peropuedeser probada duro bajo N P c o N P . Eso significaría que N P c o N P nos dice algo sobre los cálculos deterministas que P N P ya no dice; intuitivamente, esto es difícil de entender.PNPPNPNPcoNPNPcoNPPNP

Ryan Williams
fuente
Sí. Es difícil comprender que tales resultados de dureza son incluso posibles. Me preguntaba si podemos probar la inexistencia de tales resultados de dureza. Uf ... se está volviendo complicado.
Shiva Kintali
(1) Me temo que está escribiendo el caso sí y el no caso opuestamente en el segundo párrafo. Es fácil construir un algoritmo no determinista que haga lo que usted indicó (informa "todos satisfechos" en al menos una ruta si la fórmula es satisfactoria e informa "como máximo 1 − ε" en todas las rutas si la fórmula está ε-lejos de ser satisfactoria ) simplemente probando todas las asignaciones de verdad de manera no determinista. (2) Estoy de acuerdo con la parte "difícil de entender".
Tsuyoshi Ito
8

Descargo de responsabilidad: esta no es una respuesta directa.

En realidad, hay muchas más condiciones de dureza además de P! = NP y el UGC. David Johnson escribió una hermosa columna para las Transacciones sobre Algoritmos en 2006 precisamente sobre este tema. Enumera los numerosos supuestos diferentes que se utilizan para mostrar la dureza y cómo se relacionan entre sí.

Desafortunadamente, estas son todas las clases NP vs deterministas (con la excepción de NP y co-AM). NP vs co-NP no está cubierto en absoluto.

Suresh Venkat
fuente
2
Como comentario interesante, David Johnson habla de NP vs co-NP en la siguiente columna: ¡columna de integridad de NP número 26 !
Daniel Apon
ah por supuesto. Debería haberlo recordado. Pero no hay aproximaciones aunque ...
Suresh Venkat
4

es una hipótesis más fuerte que P N P desde N P C O N P implica P N P . Entonces, cualquier resultado de dureza de la aproximación suponiendo que P N P también se seguiría de lasuposiciónde N P c o N P.NPcoNPPNPNPcoNPPNPPNPNPcoNP

Mohammad Al-Turkistany
fuente
3
Es posible que NP = coNP y aún la pregunta P vs NP esté abierta. Estoy buscando un resultado de dureza de aproximación que se convertirá en falso si NP = coNP pero no se ve afectado (es decir, sigue siendo una conjetura) por P! = NP.
Shiva Kintali
AαNPcoNPα