Master d'Informatique. D22 - Complexité Algorithmique.
Exemple : X = {Bob, Tim, Buck}, Y = {Léa, Flo, May}, Z = {Durex, Manix, Lubrix}
Le problème SAT et 7 problèmes NP-complets et
1. Le problème SAT
M = {(Bob, Léa, Manix), (Bob, Flo, Lubrix), (Tim, May, Manix),
(Buck, Flo, Durex), (Buck, Léa, Durex)}
Problème SAT [satisfaisabilité] Ici q = 3 et cette instance du problème admet une solution :
Instance : Un ensemble de variables booléennes U et un ensemble de clauses C
sur U . M 0 = {(Bob, Flo, Lubrix),
Question : Existe-t-il une instanciation des variables de U qui satisfait l'en- (Tim, May, Manix),
semble des clauses de C ? (Buck, Léa, Durex)}
Exemple : U = {u1 , u2 , u3 } et C = {{u1 , u2 , u3 }, {u1 , u3 }}. Il y a trois variables et un
ensemble de deux clauses à trois et deux littéraux respectivement. Satisfaire C signi e 4. Le problème VC
aecter une valeur de vérité vrai ou faux à chacune des trois variables u1 , u2 et u3 de
telle manière que l'expression booléenne suivante soit vraie :
(u1 ∨ u2 ∨ u3 ) ∧ (u1 ∨ u3 ) Problème VC [recouvrement des sommets]
Ici, la clause est évidemment satisfaisable, il su t de prendre u1 = u2 = vrai et une Instance :Un graphe G = (X, U ) et un entier positif K ≤ |X|.
Question : Existe-t-il un recouvrement des sommets de taille inférieure à K ,
valeur de vérité quelconque pour u3 .
autrement dit un sous-ensemble Y ⊆ X , |Y | ≤ K tel que ∀(x, y) ∈ U , x ∈ Y
ou y ∈ Y ?
2. Le problème 3-SAT
c e
Problème 3-SAT [satisfaisabilité sur trois littéraux]
b
Instance : Un ensemble de variables booléennes U et un ensemble de clauses C
à trois littéraux sur U . f
Question : Existe-t-il une instanciation des variables de U qui satisfait l'en- d
semble des clauses de C ? a g
Exemple : U = {u1 , u2 , u3 , u4 } et C = {{u1 , u2 , u3 }, {u1 , u3 , u4 }}. Toutes les clauses de Dans le graphe ci-dessus et pour K = 3, il y a une solution Y = {b, e, f }. Pour K = 2
C (il y en a deux) ont exactement trois littéraux. il n'y a pas de solution.
3. Le problème 3DM
5. Le problème CL
Problème 3DM [mariage tri-dimensionnel]
Instance : Trois ensembles X , Y et Z deux-à-deux disjoints de même cardinal
q et une partie M ⊆ X × Y × Z . Problème CL [clique]
Question : Existe-t-il un mariage tri-dimensionnel, i.e. un sous-ensemble M ⊆
0 Instance : Un graphe G = (X, U ) et un entier positif K ≤ |X|.
Question : Existe-t-il une clique de taille supérieure à K , autrement dit un sous-
M de cardinal q tel que deux triplets quelconques de M dièrent sur chacune
0
des trois projections. ensemble Y ⊆ X d'au moins K sommets tels que ∀(x, y) ∈ Y × Y, (x, y) ∈ U .
1
2
SAT
b j
g
a c 3-SAT
i
e d f
3DM XC VC
Pour le graphe ci-dessus et K = 4, le problème a une solution Y = {b, c, d, e}. Pour
K = 5, il n'y a pas de solution.
PART HC CL
6. Le problème HC
Ordre des preuves de NP-complétude.
Problème HC [circuit hamiltonien]
Instance :Un graphe G = (X, U ), X = {x1 , x2 , . . . , xn }.
Question : Existe-t-il un circuit hamiltonien, c'est-à-dire une permutation π ∈
Sn telle que (xπ(1) , xπ(2) , . . . , xπ(n) , xπ(1) ) constitue un circuit du graphe.
7. Le problème XC
Problème XC [couverture exacte]
Instance :Un ensemble E et S ⊆ P(E).
Question : Existe-t-il un sous-ensemble P de S qui constitue une partition
(couverture exacte) de E ?
Exemple trivial : soit E = {1, 2, 3, 4, 5} et S = {{1, 2}, {3}, {4}, {1, 5}, {5}}. La réponse
est oui avec T = {{1, 2}, {3}, {4}, {5}}.
8. Le problème PART
Problème PART [partition]
Instance :Un ensemble ni X et une fonction taille t : X → N.
Question : Existe-t-il un sous-ensemble Y ⊆ X tel que
∑ ∑
t(x) = t(x) ?
x∈Y x∈X\Y
