MAX2SAT : la valeur d'un tirage

1. Une clause $({\ell }_1\vee {\ell }_2)$ est fausse dans le seul cas où ses deux littéraux sont faux, soit une affectation sur quatre. Elle est donc satisfaite avec probabilité $3/4$. Par linéarité de l'espérance — qui ne demande aucune indépendance entre les clauses, alors qu'elles partagent des variables :

$$\mathbb{E}[\text{clauses satisfaites}]=\sum _{j=1}^m\mathrm{Pr}[\text{clause }j\text{ satisfaite}]=\frac{3}{4}\times 200=150.$$

Mesure sur $20000$ tirages : $150,00$ clauses en moyenne. L'accord est exact à deux décimales.

2. La même chose : $150$. C'est le point le plus instructif de l'exercice. L'espérance ne dépend que du nombre de clauses, jamais de leur satisfiabilité conjointe. Sur la formule

$$(x\vee y)\wedge (x\vee \neg y)\wedge (\neg x\vee y)\wedge (\neg x\vee \neg y),$$

qui est insatisfiable, l'optimum vaut $3$ sur $4$ clauses ; la moyenne mesurée sur $200000$ tirages vaut $3,000$, soit exactement $\frac{3}{4}\times 4$. Le tirage aléatoire atteint ici l'optimum en moyenne, sur une formule qu'aucune affectation ne satisfait entièrement.

3. Non, il ne lit pas la formule. C'est ce qui rend le résultat frappant : un algorithme qui ignore complètement son entrée est une $3/4$-approximation. Il ne peut évidemment pas faire mieux que le nombre de clauses ; mais comme $OPT\le m$, on a bien

$$\mathbb{E}[ALG]=\frac{3}{4}m\ge \frac{3}{4}OPT.$$

Sur $20000$ instances tirées au hasard, le rapport exact $\mathbb{E}[ALG]/OPT$ n'est jamais descendu sous $0,7500$, et vaut exactement $3/4$ dans $15248$ cas — ceux où la formule est entièrement satisfiable, c'est-à-dire où $OPT=m$. La garantie est atteinte, elle n'est pas améliorable.