MAX-$k$-\textsc{sat} : la garantie en fonction de $k$

Une clause à $k$ littéraux sur $k$ variables distinctes est fausse dans le seul cas où les $k$ littéraux sont faux, soit une affectation sur $2^k$. Elle est donc satisfaite avec probabilité $1-2^{-k}$, et par linéarité de l'espérance :

$$\mathbb{E}[\text{clauses satisfaites}]=\left(1-\frac{1}{2^k}\right)m\ge \left(1-\frac{1}{2^k}\right)OPT.$$

Le tirage à pile ou face est donc une $(1-2^{-k})$-approximation de MAX-$k$-sat. Mesure sur $m=200$ clauses et $20000$ tirages :

La garantie s'améliore quand $k$ grandit, et elle tend vers $1$. C'est contre-intuitif au premier abord, puisque sat est réputé d'autant plus dur que les clauses sont longues — le chapitre chap:decidabilite dira que $3$-sat est np-complet alors que $2$-sat est linéaire.

Il n'y a pourtant pas de contradiction, et la distinguer est le point de l'exercice. Décider si toutes les clauses peuvent être satisfaites devient plus difficile quand $k$ croît. Approcher le maximum devient plus facile, parce qu'une clause longue est plus facile à satisfaire par hasard. Les deux problèmes sont différents ; il n'y a aucune raison qu'ils varient dans le même sens.

Le cas $k=3$ est un jalon célèbre : la garantie $7/8$ obtenue par cette analyse de trois lignes est, sous l'hypothèse $\mathrm{P}\ne \mathrm{NP}$, la meilleure possible — résultat de Håstad, très au-delà du programme. Un algorithme qui ignore son entrée fait déjà tout ce qu'on sait faire.