Probleme – MAX2SAT : du hasard au déterminisme

1. L'espérance conditionnelle se calcule exactement, et c'est le point de départ. Fixons une affectation partielle $\sigma$ des premières variables. Une clause est fausse sous $\sigma$ complétée au hasard si et seulement si aucun de ses littéraux n'est déjà vrai, et si tous ses littéraux non encore fixés tombent du mauvais côté. D'où, pour une clause $c$ :

$$\mathrm{Pr}[c\text{ fausse}\mid \sigma ]=\{\begin{array}{ll}0& \text{si un litteˊral de }c\text{ est deˊjaˋ vrai sous }\sigma ,\\ 2^{-r}& \text{sinon, ouˋ }r\text{ est le nombre de litteˊraux non fixeˊs de }c.\end{array}$$

(* Esperance du nombre de clauses satisfaites, les variables non fixees etant
   tirees a pile ou face. fixe.(i) = Some b si x_i vaut b, None sinon.
   Complexite : O(taille de la formule). *)
let esperance clauses fixe =
  Array.fold_left (fun acc cl ->
    let p_fausse = Array.fold_left (fun q (i, positif) ->
      match fixe.(i) with
      | None -> q *. 0.5                       (* litteral libre : une chance sur deux *)
      | Some b -> if b = positif then 0.0 else q   (* deja vrai : clause satisfaite *)
    ) 1.0 cl in
    acc +. (1.0 -. p_fausse)) 0.0 clauses

2. L'algorithme : la méthode des espérances conditionnelles. On fixe les variables une à une, en choisissant à chaque fois la valeur qui donne la plus grande espérance conditionnelle.

(* Affectation deterministe satisfaisant au moins 3/4 des clauses.
   Entrees : n variables, un tableau de clauses a deux litteraux distincts.
   Sortie  : un tableau de valeurs. Complexite : O(n * taille de la formule). *)
let derandomiser n clauses =
  let fixe = Array.make n None in
  for i = 0 to n - 1 do
    fixe.(i) <- Some true;  let avec_vrai = esperance clauses fixe in
    fixe.(i) <- Some false; let avec_faux = esperance clauses fixe in
    fixe.(i) <- Some (avec_vrai >= avec_faux)   (* on garde le MEILLEUR des deux *)
  done;
  Array.map (function Some b -> b | None -> false) fixe

La preuve de la garantie tient en une remarque, et c'est une belle. Notons $E(\sigma )$ l'espérance conditionnelle sous l'affectation partielle $\sigma$. En tirant $x_i$ à pile ou face,

$$E(\sigma )=\frac{1}{2}E(\sigma ,x_i=V)+\frac{1}{2}E(\sigma ,x_i=F),$$

puisque le tirage de $x_i$ n'est qu'un cas particulier du tirage de toutes les variables restantes. Une moyenne de deux nombres est majorée par le plus grand des deux :

$$\max (E(\sigma ,x_i=V),E(\sigma ,x_i=F))\ge E(\sigma ).$$

L'espérance ne décroît donc jamais le long de l'exécution. Au départ, aucune variable n'est fixée et $E(\varnothing )=\frac{3}{4}m$ ; à l'arrivée, toutes le sont, et l'espérance d'une affectation complète est le nombre exact de clauses qu'elle satisfait. Donc

$$\#\{\text{clauses satisfaites}\}=E(\text{final})\ge E(\varnothing )=\frac{3}{4}m\ge \frac{3}{4}OPT.$$

L'algorithme est déterministe, il ne tire plus rien, et il garde la garantie. On a « dérandomisé » la preuve probabiliste.

3. Les mesures, sur $3000$ instances aléatoires de $3$ à $8$ variables et $4$ à $18$ clauses, comparées à l'optimum calculé par énumération :

Le rapport ne descend jamais sous $3/4$, conformément à la preuve, et l'algorithme trouve l'optimum quatre fois sur cinq.

Complexité : $n$ tours, deux évaluations de l'espérance par tour, chacune linéaire en la taille de la formule. Total $O(n(n+m))$. On paye donc un facteur $n$ pour supprimer le hasard — c'est le prix ordinaire de la dérandomisation.

Ce que le problème enseigne, et qui vaut au-delà de MAX2SAT. La méthode probabiliste ne sert pas seulement à fabriquer un algorithme aléatoire : elle sert à prouver l'existence d'une bonne solution. Puisque la moyenne vaut $\frac{3}{4}m$, il existe forcément une affectation qui atteint au moins cette valeur — c'est un argument d'existence pur, qui ne dit pas comment la trouver. La dérandomisation transforme cet argument en construction, en descendant l'arbre des affectations sans jamais laisser l'espérance décroître.