Algorithme randomisé pour 3SAT

Il existe un algorithme aléatoire très simple qui, étant donné un 3SAT, produit une assignation satisfaisant au moins 7/8 des clauses (en attente): choisissez une assignation aléatoire. Une assignation aléatoire satisfait chaque clause avec la probabilité 7/8, et donc la linéarité de l'attente montre que la fraction attendue des clauses satisfaites par une assignation aléatoire est 7/8.

Cela peut-il être fait de manière déterministe? Si oui, pourquoi nous intéressons-nous à l'algorithme randomisé?

L'algorithme d'assignation aléatoire peut être dérandomisé (rendu déterministe) en utilisant la méthode des attentes conditionnelles.

Soit l'instance 3SAT constituée des clauses . Pendant l'algorithme, nous assignerons des valeurs aux variables. Le score d'une clause est défini comme suit:$C_1,\ldots,C_m$$C$

• Si est satisfait, son score est de 1.$C$
• Si n'est pas satisfait et a littéraux non attribués, alors son score est .$C$$k$$1-2^{-k}$

Initialement, le score de chaque clause est de , et donc le score total est de . Nous attribuons maintenant des valeurs aux variables dans l'ordre. Supposons que nous avons assigné des valeurs aux variables , et que le score total actuel est . Soit le score total si nous attribuons les valeurs (respectivement) à . Je prétends que pour toute clause , et donc . En effet:$1-2^{-3} = 7/8$$(7/8) m$$x_1,\ldots,x_n$$x_1,\ldots,x_{i-1}$$S = S(C_1)+\cdots+S(C_m)$$S_0,S_1$$0,1$$x_i$$S_0(C)+S_1(C) = 2S(C)$$C$$S_0 + S_1 = 2S$

• Si est satisfait (uniquement ) ou ne contient pas alors .$C$$x_1,\ldots,x_{i-1}$$x_i$$S_0(C) + S_1(C) = 2S(C)$
• Supposons que contienne littéraux non attribués, y compris . Alors , , et . Par conséquent, $C$$k$$x_i$$S(C) = 1-2^{-k}$$S_0(C) = 1-2^{-(k-1)}$$S_1(C) = 1$ $$S_0(C) + S_1(C) = [1 - 2 \cdot 2^{-k}] + 1 = 2(1 - 2^{-k}) = 2S(C).$$
• Un argument similaire fonctionne lorsque contient . $C$$\bar{x}_i$

Puisque , ou (éventuellement les deux). Par conséquent , il y a une certaine affectation à de telle sorte qu'après la cession, le score est au moins .$S_0 + S_1 = 2S$$S_0 \geq S$$S_1 \geq S$$S$$S$

Le score initial est de et l'algorithme garantit que le score ne diminue jamais. A la fin, le score d'une clause est 1 si elle est satisfaite et sinon. Ainsi, l'affectation finale satisfait au moins clauses.$(7/8)m$$C$$1-2^{-0}=0$$(7/8)m$

Étant donné qu'il existe un algorithme déterministe, pourquoi nous intéressons-nous à l'algorithme aléatoire? Il existe plusieurs raisons:

1. L'algorithme randomisé est beaucoup plus simple.
2. L'algorithme randomisé est potentiellement plus rapide.
3. L'algorithme randomisé peut être converti en algorithme déterministe en utilisant la méthode des attentes conditionnelles; on peut y penser comme une recette pour construire un algorithme déterministe.

Plus généralement, on suppose que chaque algorithme de polytime aléatoire pour un problème de décision peut être dérandomisé (il s'agit de la conjecture ). Les algorithmes randomisés seront toujours intéressants pour toutes les raisons énumérées ci-dessus.$\mathsf{P}=\mathsf{BPP}$