Rappel :

Trouver une interprétation qui rende vraie un ensemble de clauses c'est trouver
une interprétation qui rende vraie toute clause de l'ensemble.

Une clause est une disjonction de littéraux : pour rendre vraie la clause toute
entière il suffit de rendre vraie un de ses littéraux. Ici, on ne travaille que sur
des clauses qui ont au plus deux littéraux (de la forme p ou q).

Dans la suite, on posera P : " B, un ensemble de clauses, k' un entier : existe-t-il
une interprétation I dans laquelle au plus k' lettres propositionnelles prennent
la valeur vrai ? "

Preuve que le problème P considéré est dans la classe NP :

Etant donnée une interprétation quelconque des variables présentes dans les
clauses de l'ensemble B consideré, on vérifie en un temps linéaire par rapport
au nombre des variables si cette interprétation convient ou pas.

Preuve que le problème P est NP-Complet :

On réduit le problème du stable à P.

Soit (G,k) une instance du stable où G = (U,A), U : ensemble de sommets,
A : ensemble d'arêtes.
On le transforme en une instance de P (B,k') où :

• Si A est non vide, alors B est un ensemble de clauses
  avec exactement deux litteraux tel que les variables propositionnelles
  sont les sommets de G et :
  a) s'il y a une arête entre les deux sommets p et q, alors p OU q
  est une clause de B
  b) si L OU L' est une clause de B, alors L et L' sont,
  respectivement deux sommets p et q tels qu'il existe une arête entre p et q.
  
  
• Si A est vide, alors B est consistué d' une unique clause, contenant un
  unique litteral, la constante logique "vrai".
  
  
• k' = taille(U) - k

"G a un stable d'au moins k sommets" <=> "Il existe une interprétation I qui rende B
satisfaisable avec au plus k' variables propositionnelles "positionnées" à vrai".

Preuve de " => "

Soit S un stable (ensemble de sommets) d'au moins k sommets de G.
Soit I l'interprétation :

• I(x) = V si x n'est pas dans S.
• I(x) = F si x appartient à S.

I est bien définie :

Si I n'est pas bien définie alors il existe un sommet x tel que I(x) =V et I(x) =F
c'est à dire qu'on peut trouver un x qui soit dans S et qui n'y soit pas en même temps !
Absurde.


L' interprétation I rend B satisfaisable :

Pour toute clause de B : (x ou y) : x ou bien y au plus est dans S ( s'ils sont tous les
deux dans S, ils ne sont pas reliés par une arête (propriété d'un stable) et donc ils
n'interviennent pas dans une même clause : absurde) => x ou bien y (au plus) prend
la valeur faux => x ou y au moins prend la valeur vrai => B est satisfaite par I.


Au plus k' variables propositionnelles positionnée à vrai :

Au moins k sommets de G sont dans S, au moins k variables de B prennent la valeur
faux donc au plus taille(U) - k = k' variables prennent la valeur vrai.

Preuve de " <= "

Soit I une interprétation telle qu'au plus k' variables de B sont vraies et telle que I(B)=vrai.

Soit S l'ensemble des variables fausses.

S a au moins k sommets :

Au plus k' variables de B sont vraies => au moins k variables sont fausses. taille(S) >= k'.

S est un stable :

Par l'absurde : S n'est pas un stable => il existe deux sommets x et y dans S qui
sont reliés par une arête. Or, x et y sont interprétés par I à faux, s'ils sont reliés
par une arête c'est qu'ils apparaissent dans une même clause et donc cette clause
est une clause fausse de B. Donc B n'est pas satisfaite par I : absurde.

Preuve que la transformation de l'instance du problème du stable à l'instance de P est polynomial :

L'ensemble B de clauses se construit en temps polynomial par rapport
au nombre d'arêtes de G :0).

La rédaction de cette correction a été faite par Sarah Cohen Boulakia.