Problème — 2-sat : pourquoi le saut se fait entre 2 et 3 — exercice corrigé d'informatique (MP2I/MPI) (chapitre 20)

1. Les deux arcs. La clause $(ℓ_{1} \lor ℓ_{2})$ est équivalente à $\neg ℓ_{1} \to ℓ_{2}$ , et aussi à $\neg ℓ_{2} \to ℓ_{1}$ — c'est la même formule lue dans les deux sens. On pose donc les arcs

$\neg ℓ_{1} ⟶ ℓ_{2} et \neg ℓ_{2} ⟶ ℓ_{1} .$

Il en faut deux, et c'est le point de départ. Un seul arc encoderait une implication, pas une disjonction : on perdrait la moitié de l'information, et le graphe cesserait d'être symétrique — propriété dont la preuve a besoin. Le graphe obtenu vérifie : $u \to v$ est un arc si et seulement si $\neg v \to \neg u$ en est un. C'est la contraposée, devenue une symétrie du graphe.

◆Théorème 20.1Critère de

2

-satisfiabilité

Une fnc à deux littéraux par clause est satisfiable si et seulement si aucune variable $p$ n'a $p$ et $\neg p$ dans la même composante fortement connexe du graphe d'implication.

Démonstration

( $\Rightarrow$ , par contraposée) Supposons $p$ et $\neg p$ dans la même composante fortement connexe : il existe un chemin $p ⇝ \neg p$ et un chemin $\neg p ⇝ p$ . Or un arc $u \to v$ signifie « tout modèle qui rend $u$ vrai rend $v$ vrai », et cette propriété se transmet le long d'un chemin. Si un modèle rendait $p$ vraie, le premier chemin le forcerait à rendre $\neg p$ vraie ; s'il rendait $p$ fausse, donc $\neg p$ vraie, le second le forcerait à rendre $p$ vraie. Aucun modèle n'existe.

( $\Leftarrow$ ) On construit un modèle. Contractons les composantes fortement connexes : le graphe quotient est sans circuit (chapitre chap:graphes-avances), donc admet un tri topologique. Posons $p := V$ lorsque la composante de $p$ vient après celle de $\neg p$ dans ce tri, et $p := F$ sinon — ce qui a un sens puisque les deux composantes sont distinctes par hypothèse. La symétrie du graphe garantit que cette affectation est cohérente, et qu'aucun arc ne mène d'un littéral vrai à un littéral faux ; toutes les clauses sont donc satisfaites.

3. La complexité. Le graphe a $2 n$ sommets et $2 m$ arcs ; les composantes fortement connexes se calculent en $Θ (V + E)$ par l'algorithme de Kosaraju ou celui de Tarjan (chapitre chap:graphes-avances), et le tri topologique aussi. Total : $Θ (n + m)$ — linéaire, comme annoncé.

Mesures. Le critère a été confronté à une recherche exhaustive sur $2000$ instances tirées au hasard ( $2$ à $5$ variables, $1$ à $10$ clauses) : accord dans tous les cas. Trois exemples :

Formule	Composantes	Verdict
$(p \lor q) \land (\neg p \lor q) \land (p \lor \neg q)$	$2$	satisfiable
la même $\land (\neg p \lor \neg q)$	$1$	insatisfiable
$(p \lor \neg q) \land (q \lor \neg r) \land (r \lor \neg p) \land (\neg p \lor \neg r)$	$2$	satisfiable

La deuxième ligne est instructive : les quatre clauses sur deux variables forment l'antilogie $δ$ de l'exercice 20.3, et le graphe le voit — les quatre littéraux s'effondrent en une seule composante, où $p$ et $\neg p$ se retrouvent donc ensemble.

Pourquoi cela s'arrête à deux littéraux. Toute la construction repose sur ceci : une clause de deux littéraux équivaut à une implication entre un littéral et un littéral. Avec trois littéraux, $(ℓ_{1} \lor ℓ_{2} \lor ℓ_{3})$ se lit $\neg ℓ_{1} \to (ℓ_{2} \lor ℓ_{3})$ : la conclusion n'est plus un littéral mais une disjonction, et il n'y a plus d'arc à poser. On n'obtient pas un graphe mais un hypergraphe, où la fermeture transitive n'est plus calculable en temps polynomial — et de fait, $3$ -sat est np-complet (chapitre chap:decidabilite). Le saut de $2$ à $3$ est un saut de structure, pas de taille.

Problème — $2$ -sat : pourquoi le saut se fait entre $2$ et $3$

Énoncé

Corrigé

Exercices semblables