Lacunas difíceis nos problemas de satisfação de restrição máxima?

12

Uma formulação equivalente do teorema de PCP é: Para Max 3-SAT, é difícil distinguir entre fórmulas satisfatórias e fórmulas onde, no máximo, a fração das cláusulas é satisfatória (para alguns ).NPrr<1

Existe algum teorema de dicotomia conhecido que classifique todo o CSP Max com base em se eles têm lacunas ou não?

Edit 16 Dec 2010 : MAX CSP with hard gap significa que o problema possui um fator ideal de falta de proximidade. Por exemplo, o 3SAT possui uma lacuna difícil no local um, pois é um tempo polinomial aproximado de um fator mas é difícil obter o fator de aproximação mesmo quando todas as cláusulas são satisfatórias.7/8NP7/8+ϵ

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

Respostas:

18

Prasad Raghavendra, no melhor artigo do STOC'08, provou ser uma conjectura de dicotomia para aproximar o Max-CSP assumindo a Conjectura de Jogos Exclusivos. Não foi assim que ele a apresentou originalmente, mas ele deu palestras apresentando as coisas dessa maneira alguns anos depois, por exemplo, no IAS, onde foi filmado: http://www.math.ias.edu/seminars/abstract ? event = 36669

A diferença de mostrar a dureza do SNP é que aqui falamos de resultados quantitativamente ótimos.

Dana Moshkovitz
fonte
3
o que significa 'quantitativamente ideal'?
Suresh Venkat
3
fator de dureza que coincide com o melhor algoritmo de aproximação conhecido
Dana Moshkovitz
6

O teorema 5.14 de Khanna, Sudão, Trevisan e Williamson [KSTW01] fornece um teorema de dicotomia para as versões gap com perfeição completa para os problemas booleanos do MaxCSP.

[KSTW01] Sanjeev Khanna, Madhu Sudão, Luca Trevisan e David P. Williamson. A aproximabilidade de problemas construtivos de satisfação. SIAM Journal on Computing , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948

Tsuyoshi Ito
fonte
Papel interessante. Como esse teorema da dicotomia está relacionado ao resultado de Raghavendra na resposta de Dana?
Mohammad Al-Turkistany
Eu acho que os resultados são bastante diferentes. O teorema de [KSTW01] que mencionei nesta resposta é sobre a versão perfeita, enquanto o resultado de Raghavendra não é. O teorema em [KSTW01] é sobre CSP booleano, enquanto o de Raghavendra é sobre CSP em qualquer domínio. Mas você deve verificar por si mesmo, porque não conheço bem o trabalho de Raghavendra.
Tsuyoshi Ito
4

Se não me engano, o resultado definitivo dessa frente é de Nadia Creignou, que mostrou que todos os problemas no MAX CSP são solucionáveis ​​em politima ou em hardwares MAX SNP .

Suresh Venkat
fonte
O MAX 2-SAT é resistente ao MAX SNP, mas é facilmente solucionável em casos satisfatórios (2-SAT enquanto 3-SAT não é conhecido por ). É difícil ter uma aproximação de 7/8 para Max 3-SAT, mesmo em instâncias satisfatórias (para qualquer ). P N P 7 / 8 + £ £ > 0∈PPNP7/8+ϵϵ>0
Mohammad Al-Turkistany