La clause qui répète une variable

Les deux cas se comportent à l'opposé.

• $(x\vee \neg x)$ est une tautologie : elle est satisfaite avec probabilité $1$. Mesure sur $100$ clauses de cette forme : moyenne $100,00$ — l'algorithme aléatoire est optimal.
• $(x\vee x)$ équivaut à $x$ : elle est satisfaite avec probabilité $1/2$, et non $3/4$.

Et c'est là que la garantie tombe. Sur une instance faite de $100$ clauses toutes égales à $(x\vee x)$ :

$$\mathbb{E}[ALG]=50\text{(mesureˊ : }49,83\text{)},OPT=100\text{(prendre }x=V\text{)}.$$

Le rapport vaut $1/2$, pas $3/4$. L'hypothèse « deux variables distinctes » n'est pas un détail de rédaction : c'est elle qui porte la garantie.

Comment la rétablir. Deux remèdes, tous deux honnêtes.

• Normaliser la formule avant de la traiter : remplacer $(x\vee x)$ par la clause unitaire $(x)$, et supprimer les tautologies $(x\vee \neg x)$. On obtient une instance de MAX-$k$-sat mixte, et l'analyse de l'exercice « MAX-$k$-sat » donne la garantie $1-2^{-k_{\min }}$ où $k_{\min }$ est la plus petite longueur de clause — soit $1/2$ s'il reste des clauses unitaires. La garantie est plus faible, mais elle est vraie.
• Restreindre le problème en exigeant des variables distinctes, ce que fait la définition standard de MAX2SAT.

La leçon dépasse cet exemple. Une garantie d'approximation est un théorème, avec des hypothèses. Le chapitre insiste : « la garantie porte sur toutes les instances » — mais toutes les instances du problème tel qu'il est défini. Une instance qui sort de la définition sort de la garantie, et rien ne le signalera à l'exécution. C'est exactement la discipline de spécification du chapitre chap:discipline, appliquée à un théorème plutôt qu'à une fonction.