Lagunas difíciles en los problemas de satisfacción de restricción máxima?

12

Una formulación equivalente del teorema de PCP es: para Max 3-SAT es -duro distinguir entre fórmulas satisfactorias y fórmulas donde, como máximo, la fracción r de las cláusulas es satisfactoria (para algunos r < 1 ).NPrr<1

¿Existe algún teorema de dicotomía conocido que clasifique todos los CSP máximos en función de si tienen brechas o no?

Editar 16 de diciembre de 2010 : MAX CSP con brecha dura significa que el problema tiene un factor de aproximación óptimo. Por ejemplo, 3SAT tiene brecha duro en la posición uno, ya que es polinomio approximable tiempo a un factor de pero es N P -difícil para obtener factor de aproximación 7 / 8 + ε incluso cuando todas las cláusulas son satisfiable.7/8NP7/8+ϵ

cc.complexity-theory pcp csp Mohammad Al-Turkistany
fuente

Respuestas:

18

Prasad Raghavendra en el mejor artículo de STOC'08 demostró una conjetura de dicotomía para aproximar Max-CSP asumiendo la Conjetura de juegos únicos. No es así como lo presentó originalmente, pero dio charlas presentando las cosas de esta manera un par de años más tarde, por ejemplo, en el IAS, donde fue grabado en video: http://www.math.ias.edu/seminars/abstract ? event = 36669

La diferencia de mostrar dureza SNP es que aquí hablamos de resultados cuantitativamente óptimos.

Dana Moshkovitz
fuente
3
¿Qué significa "cuantitativamente óptimo"?
Suresh Venkat
3
factor de dureza que coincide con el algoritmo de aproximación más conocido
Dana Moshkovitz el
6

El teorema 5.14 de Khanna, Sudán, Trevisan y Williamson [KSTW01] proporciona un teorema de dicotomía para las versiones gap con una integridad perfecta para los problemas booleanos de MaxCSP.

[KSTW01] Sanjeev Khanna, Madhu Sudán, Luca Trevisan y David P. Williamson. La aproximabilidad de los problemas de satisfacción restrictiva. SIAM Journal on Computing , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948

Tsuyoshi Ito
fuente
Interesante papel. ¿Cómo se relaciona este teorema de dicotomía con el resultado de Raghavendra en la respuesta de Dana?
Mohammad Al-Turkistany
Creo que los resultados son bastante diferentes. El teorema en [KSTW01] que mencioné en esta respuesta es sobre la versión de integridad perfecta, mientras que el resultado de Raghavendra no lo es. El teorema en [KSTW01] trata sobre CSP booleano, mientras que Raghavendra trata sobre CSP sobre cualquier dominio. Pero deberías comprobarlo tú mismo, porque no conozco bien el artículo de Raghavendra.
Tsuyoshi Ito