De fortes lacunes dans les problèmes de satisfaction maximale des contraintes?

12

Une formulation équivalente du théorème PCP est: Pour Max 3-SAT, il est -hard de faire la distinction entre les formules satisfaisables et les formules où au plus r -fraction des clauses sont satisfaisables (pour certains r < 1 ).NPrr<1

Existe-t-il un théorème de dichotomie connu qui classe tous les CSP Max en fonction de leur absence ou non?

Edit 16 décembre 2010 : MAX CSP avec un espace dur signifie que le problème a un facteur d'inapproximabilité optimal. Par exemple, 3SAT a gap dur à l' emplacement , car il est une approximable polynomial à un facteur mais il est N P -Hard pour obtenir le facteur de rapprochement 7 / 8 + ε , même lorsque tous les articles sont satisfaisable.7/8NP7/8+ϵ

cc.complexity-theory pcp csp Mohammad Al-Turkistany
la source

Réponses:

18

Prasad Raghavendra dans le meilleur article STOC'08 s'est avéré une conjecture de dichotomie pour approximer Max-CSP en supposant la conjecture des jeux uniques. Ce n'est pas ainsi qu'il l'a présenté à l'origine, mais il a fait des exposés présentant les choses de cette façon quelques années plus tard, par exemple, à l'IAS, où il a été enregistré sur vidéo: http://www.math.ias.edu/seminars/abstract ? event = 36669

La différence par rapport à la dureté SNP est que nous parlons ici de résultats quantitativement optimaux.

Dana Moshkovitz
la source
3
que signifie «quantitativement optimal»?
Suresh Venkat
3
facteur de dureté correspondant à l'algorithme d'approximation le plus connu
Dana Moshkovitz
6

Le théorème 5.14 de Khanna, Soudan, Trevisan et Williamson [KSTW01] donne un théorème de dichotomie pour les versions de lacune avec une parfaite complétude pour les problèmes booléens MaxCSP.

[KSTW01] Sanjeev Khanna, Madhu Soudan, Luca Trevisan et David P. Williamson. L'approximation des problèmes de satisfaction des constructeurs. SIAM Journal on Computing , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948

Tsuyoshi Ito
la source
Papier intéressant. Comment ce théorème de dichotomie est-il lié au résultat de Raghavendra dans la réponse de Dana?.
Mohammad Al-Turkistany,
Je pense que les résultats sont assez différents. Le théorème de [KSTW01] que j'ai mentionné dans cette réponse concerne la version complète parfaite alors que le résultat de Raghavendra ne l'est pas. Le théorème de [KSTW01] concerne le CSP booléen, tandis que celui de Raghavendra concerne le CSP sur n'importe quel domaine. Mais vous devriez vérifier par vous-même, car je ne connais pas bien le papier de Raghavendra.
Tsuyoshi Ito