Problème CE

Nous allons montrer que le problème Couverture Exacte est NP-complet

Illustrons ce problème en reprenant un exemple tiré de Wikipédia :

• $U = \{1, 2, 3, 4, 5, 6, 7\}$
• $\mathcal{S} = \{ \{1, 4, 7\}, \{1, 4\}, \{4, 5, 7\},\{3, 5, 6\},\{2, 3, 6, 7\},\{2, 7\} \}$

Résoudre ce problème revient à faire plein de choix. Parfois ces choix sont simple : si on place $\{1, 4, 7\}$ on ne peut plus mettre que la classe $\{3, 5, 6\}$ qui ne forme pas une partition ; parfois les choix sont plus cornéliens : doit-on placer la classe $\{3, 5, 6\}$, ce qui empêche d'utiliser la classe $\{4, 5, 7\}$ (par exemple) ? Ou ne pas la mettre ? A priori on ne sais pas.

Prouver que le problème de Couverture Exact (CE) est NP-Complet va être plus facile que celle du théorème de Cook/Levin. En effet, maintenant que l'ensemble des problème NP-complet est non vide (il y a au moins SAT dedans), pour montrer qu'un problème $A$ est NP-complet il nous suffit maintenant de :

1. choisir un problème $B$ NP-complet
2. montrer qu'il existe une réduction polynomiale $B \leq A$

En effet, si $C$ est un problème quelconque de NP, on a $C\leq B$ (par définition de l'ensemble NP-complet) ce qui amène par transitivité de la réduction polynomiale à $C \leq A$.

Pour l'instant nous ne connaissons qu'un problème NP-Complet : SAT. Montrons donc que $SAT \leq CE$.

Les réductions pour montrer qu'un problème est NP-complet peuvent être étrange au premier regard. Elles nécessitent souvent des constructions baroques pour associer un problème à l'autre. On appelle ces constructions des gadget. Ceci est normal car on essaie de mettre en regard deux problèmes qui n'ont souvent rien à voir. On va le faire ici en mettant en parallèle un problème de logique SAT et un problème de recherche de sous-ensemble CE.

Gadget

On considère une instance de SAT que l'on va transformer polynomialement en une instance de CE. Posons ses paramètres :

• $x_1, \dots, x_n$ : les $n$ variables booléennes
• $c_1 \land \dots \land c_m$ : les $m$ conjonctions de clauses
• $c_i = l^1_i \lor \dots \lor l^{k_i}_i$ : les littéraux formant les clauses.

On suppose de plus sans perte de généralité que :

1. il n'existe pas de clause ayant à la fois $x_i$ et $\overline{x_i}$ comme littéral (sinon cette clause est trivialement toujours vérifiée)
2. pour toute variable booléenne $x_i$ il existe une clause ayant $x_i$ comme littéral et une autre clause ayant $\overline{x_i}$ (sinon il suffit de mettre la modalité de $x_i$ à celle apparaissant dans les clauses pour les rendre trivialement vraies)

Notez que l'on peut transformer toute instance de $SAT$ en une instance satisfaisant les deux conditions ci-dessus en supprimant les clauses satisfaisant la première condition et en supprimant la variable booléenne satisfaisant la seconde condition. Cette transformation se fait en temps polynomial par rapport à l'entrée de $SAT$.

On peut maintenant transformer cette instance de $SAT$ en une instance de $CE$ ayant comme entrée :

L'ensemble de $CE$ couvre tous les éléments de $SAT$ : les variables booléennes, les clauses et les littéraux. Les classes forment les liens entre les différents éléments : pour chaque $x_i$ les littéraux valant $x_i$, pour chaque $x_i$ les littéraux valant $\overline{x_i}$ et pour chaque clause l'ensemble de ses littéraux. Cette construction est bien polynomiale par rapport à la taille de l'entrée du problème $SAT$.

Notre gadget transforme L'instance exemple SAT en une instance de $CE$.

Formule SAT originelle :

Entrée de CE associée :

Nous allons montrer sur l'exemple que ce gadget fonctionne. Je cas général en découlera de lui-même. Il faut faire deux choses :

1. montrer que si le problème de CE admet une solution alors le problème SAT originel aussi
2. montrer que si le problème de CE n'admet pas de solution alors le problème SAT originel non plus

On montre très souvent la 2. condition par la réciproque (montrer que montrer que si le problème SAT originel admet une solution alors le problème CE aussi), ce qui permet d'être symétrique :

• Si CE à une solution alors SAT aussi
• Si SAT à une solution alors CE aussi

Solution de CE vers une solution de SAT

Pour comprendre comment une solution de CE permet de trouver une solution de SAT, reprenons notre exemple et cherchons une partition solution. Il en existe plusieurs, par exemple :

Pour repasser de cette solution de CE à une solution de SAT, regardons comment elle est construite :

• il faut que la partition contienne les $c_i$ : de part la construction de $\mathcal{S}$ ceci signifie que la classe contenant $c_i$ va également contenir 1 $l_i^j$.
• il faut que la partition contienne les $x_i$ : de part la construction de $\mathcal{S}$ ceci signifie que la classe contenant $x_i$ va également contenir des $l_j^k$. Attention ces $l_j^k$ ne doivent pas être celui choisi dans la classe contenant $c_j$
• tous les autres littéraux pouvant être attribués comme on le souhaite on peut les "oublier".

Pour notre exemple ceci donne :

Remarquez que le choix de la classe contenant la clause contraint la classe contenant la variable. En choisissant $\{c_1, l_1^1\}$ je force le choix de $\{x_1, l_2^1, l_3^1\}$ puisque $l_1^1 = x_1$. Vous venez de découvrir le gadget : la classe contenant $c_i$ force le choix pour $x_j$ en prenant le littéral opposé.

Comme une solution de SAT doit avoir au moins 1 littéral de vrai par clause, regardons ce qu'il se passe si on suppose que c'est celui choisi dans la clause est vrai. Dans l'exemple :

• $l_1^1$ est vrai donc $x_1$ est vrai
• $l_2^2$ est vrai donc $\overline{x_2}$ est vrai
• $l_3^2$ est vrai donc ${x_3}$ est vrai
• $l_4^1$ est vrai donc ${x_1}$ est vrai

On ne peut pas arriver àla conclusion qu'une variable booléenne est vrai et fausse, car sinon il est impossible de choisir une classe contenant cette variable : c'est le principe du gadget qui implique que ces choix sont cohérents avec les classes contenant les $x_i$ (qui correspondent aux littéraux faux).

On sait déjà que $x_1$, $\overline{x_2}$ et ${x_3}$ sont vrais. Pour connaître la valeur des autres variables, on regarde les classes choisies :

• ${x_1, l_2^1, l_3^1}$ donc $l_2^1 = \overline{x_1}$ et $l_3^1 = \overline{x_1}$ sont faux donc $x_1$ est vrai (ouf, c'est cohérent)
• ${x_2, l_1^2}$ donc $l_1^2 = {x_2}$ est faux (c'est cohérent)
• ${x_3, l_2^3, l_4^2}$ donc $l_2^3 = l_4^2 = \overline{x_3}$ est faux : $x_3$ est vrai (c'est cohérent)
• ${x_4, l_3^3}$ donc $l_3^3 = {x_4}$ est faux. On ne le savait pas encore
• ${x_5, l_3^4}$ donc $l_2^3 = l_3^4 = \overline{x_5}$ est faux : ${x_5}$ est vrai.

Au final, avoir une partition nous garantit que le problème SAT originel a une solution et la donne !

On reconstruit cette solution en temps (clairement) polynomial.

Solution de SAT vers une solution de CE

Il faut maintenant montrer que si notre instance de $SAT$ à une solution alors notre instance de $CE$ en a également une.

Il suffit de faire la même chose que pour l'analyse précédente. Si l'instance de SAT a une solution, chaque clause $c_i$ possède au moins un littéral $l_i^{v(i)}$ qui est vrai. On peut alors considérer l'ensemble des classes formé de l'union de :

• $\{c_i, l_i^{v(i)}\}$ pour tout $ 1\leq i \leq m$,
• Considérons ensuite chaque littéral $l_i^j$ avec $ j \neq v(i)$ pour la solution de SAT. On a deux cas :
  • soit $l_i^j$ est vrai et on ajoute $\{ l_i^j\}$ à la solution de $CE$
  • soit $l_i^j$ est faux et on ajoute l'unique classe de $\mathcal{F}$ contenant $\{x_i, l_i^j\}$ à la solution de $CE$

De part nos hypothèses sur l'entrée de $SAT$ il est clair que cet ensemble de classes forme une solution à notre problème de $CE$. De plus, la construction de cette solution est bien polynomiale.

Conclusion

On vient de prouver $SAT\leq CE$ car :

1. $CE$ est dans NP
2. il existe une réduction polynomiale de SAT vers CE