informatique (MP2I/MPI) · Chapitre 25 · Exercice de TD
MAX2SAT : la valeur d'un tirage
Algorithmes probabilistes, approximation, séparation et évaluation · niveau 2
Énoncé
Une formule a clauses, chacune à deux littéraux portant sur deux variables distinctes. On tire chaque variable à pile ou face.
- Combien de clauses satisfaites en espérance ?
- Que vaut cette espérance sur une formule insatisfiable ?
- L'algorithme lit-il la formule ?
Corrigé
1. Une clause est fausse dans le seul cas où ses deux littéraux sont faux, soit une affectation sur quatre. Elle est donc satisfaite avec probabilité . Par linéarité de l'espérance — qui ne demande aucune indépendance entre les clauses, alors qu'elles partagent des variables :
Mesure sur tirages : clauses en moyenne. L'accord est exact à deux décimales.
2. La même chose : . 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
qui est insatisfiable, l'optimum vaut sur clauses ; la moyenne mesurée sur tirages vaut , soit exactement . 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 -approximation. Il ne peut évidemment pas faire mieux que le nombre de clauses ; mais comme , on a bien
Sur instances tirées au hasard, le rapport exact n'est jamais descendu sous , et vaut exactement dans cas — ceux où la formule est entièrement satisfiable, c'est-à-dire où . La garantie est atteinte, elle n'est pas améliorable.
