Conditions de tractabilité de la satisfaction 3SAT

Ce que je me demande précisément, c'est s'il existe une condition intéressante sur le pourcentage d'affectations qui satisfont à une formule 3SAT pour garantir que ces problèmes sont traitables.

Supposons par exemple la classe de problèmes 3SAT que des affectations possibles satisfont la formule booléenne; pouvons-nous trouver efficacement une affectation satisfaisante? Pour quel est le problème résultant de P? $\epsilon(n) 2^n$ $2^n$ $\epsilon$

Modifier la note: remplacé par pour dissiper la confusion. $\epsilon$ $\epsilon(n)$

cc.complexity-theory ds.algorithms sat np Rafi Witten
la source

Une observation simple: si

est au plus petit polynomial inverse, alors échantillonner uniformément

fois donnera une solution dans le temps polynomial attendu. Donc si

est compris entre 1 et 1 / poly (n), ce problème est facile (c'est en ZPP).

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

ϵ

$\epsilon$

Robin Kothari

de même, si 1 / eps est quasipolynomial, alors vous avez un algorithme de temps de quasipole aléatoire, ce qui lui-même serait surprenant

Suresh Venkat

Réponses:

Oui. Si est une constante (ou ), et on vous promet qu'au moins de toutes les affectations possibles satisfont les 3CNF d'entrée, alors vous pouvez trouver une telle affectation dans le polynôme déterministe- temps. $0< \epsilon <1$ $1/\textit{polylog}(n)$ $\epsilon 2^n$

Les algorithmes ne sont pas difficiles:

Revendication: En vertu de la promesse a déclaré, il doit exister une taille constante ensemble de variables qui frappe toutes les clauses du 3CNF, en ce sens que tous les 3 article doit contenir une variable de . $S$ $S$

Preuve de revendication (esquisse): Sinon, il doit exister une famille suffisamment grande de 3 clauses du 3CNF, dans laquelle chaque variable n'apparaît qu'une seule fois. Mais cette famille, lorsqu'elle est suffisamment grande, a déjà moins de fraction d'affectations satisfaisantes. QED $\epsilon$

Ainsi, vous pouvez exécuter sur tous les possibles (nombre constant) des affectations à . Sous chaque affectation fixe à , le 3CNF devient un 2CNF, en supposant que frappe le 3CNF d'origine. Maintenant, vous pouvez utiliser l'algorithme déterministe polytime connu pour trouver une affectation satisfaisante pour les formules 2CNF. Dans l'ensemble, vous obtenez une limite supérieure de temps polynomial. $S$ $S$ $S$

L'algorithme pour 2SAT est, je pense, déjà dans le célèbre article de 1971 de S. Cook.

L'algorithme pour les 3CNF provient de: L. Trevisan Une note sur le comptage approximatif déterministe pour k-DNF dans Proc. de APPROX-RANDOM, Springer-Verlag, page 417-426, 2004

L'article original montrant le résultat pour 3CNF est: E. Hirsch, Un algorithme déterministe rapide pour les formules qui ont de nombreuses affectations satisfaisantes , Journal of the IGPL, 6 (1): 59-71, 1998

Iddo Tzameret
la source

ϵ

$\epsilon$

ϵ = 1 / p o l y l o g (n)

$\epsilon = 1/polylog(n)$

Comment construisez-vous S?

Radu GRIGore

C_{1}

$C_1$

C_{2}

$C_2$

C_{1}

$C_1$