NP-COMPLÉTUDE
PARTIE I:
RAPPEL SUR LA COMPLEXITÉ
PLAN DE LA PARTIE I
Introduction
Définitions
Type de la Complexité
Notation de de Landau
Classes de complexité
Calcul de la Complexité des algorithmes (itératifs
& récursifs)
3
INTRODUCTION
Le temps d’exécution d’un algorithme dépend des facteurs
suivants :
Les données du programme,
La qualité du compilateur (langage utilisé),
La machine utilisée (vitesse, mémoire, ),
La complexité de l’algorithme lui-même,
On cherche à mesurer la complexité d’un algorithme
indépendamment de la machine et du langage utilisés, c.-
à-d. uniquement en fonction de la taille des données que
4
l’algorithme doit traiter.
INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME
Soit P(X) un polynôme de degré n
P(X) = anXn + an-1Xn-1 + ... + a1X + a0 ,
Où: n : entier naturel
an, an-1, ..., a1, a0 : les coefficients du polynôme qui sont
stockés dans le tableau T[0..n] d’entiers.
Ecrire la fonction Calcul_poly(T: Tableau[0..n]d’entier,
5
X:entier): entier.
INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME
2ème variante
1ère variante
Début
Début
Inter1
P0
P 0
Pour i 0 à n faire
Pour 0 à n faire
P P+ T[i] * Puiss (X, i)
P P+ Inter *T[i]
FP
Inter Inter * X
Fin
FP
1ère Complexité : Fin
(n+1) additions 2ème Complexité :
(n+1) multiplications (n+1) additions
(n+1) puissances 2(n+1) multiplications
6
Au moins 3 variables 3 variables
INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME
3ème variante: Schéma de Horner
P(X) = anXn + an-1Xn-1 + ... +a2X2 + a1X + a0
=(anXn-1 + an-1Xn-2 + ... +a2X + a1)X + a0
= ((anXn-1 + an-1Xn-2 + ... +a2)X+ a1)X + a0
= ............
= (....(((anX + an-1)X+ an-2 )X.....)X+ ... +a2)X+ a1)X + a0
3ème variante
Début
P T[n] 3ème Complexité :
Pour i n-1 à 0 faire n additions
P P*X + T[i] n multiplications
7
FP 2 variables
Fin
INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME
Variantes Première Deuxième Troisième
Complexité (n+1) additions (n+1) additions n additions
en temps
(en terme de (n+1) multiplications 2(n+1) n multiplications
nombre (n+1) puissances multiplications
d’opérations)
Complexité P, i et les variables P, i et Inter P, i
en espace
mémoire de la fonction
(Variables) puissance appelée
(n+1) fois
Nécessité d’estimer la complexité en temps et en
espace d’un algorithme avant de l’écrire et8
l’implémenter
DÉFINITION
La complexité (temporelle) d’un algorithme est la
mesure du nombre d’opérations fondamentales
(affectations, comparaisons, opérations arithmétiques)
qu’il effectue sur un jeu de données. Elle est exprimée
comme une fonction de la taille du jeu de données.
Elle permet en particulier de comparer deux algorithmes traitant
le même calcul. En d’autres termes, elle permet de déterminer si
un algorithme A et meilleur qu’un algorithme B
indépendamment de la machine, du langage de programmation,
du compilateur et des détails d’implémentation. 9
TYPE DE LA COMPLEXITÉ
Complexité au Complexité en Complexité au
meilleur moyenne pire
•C'est le plus petit nombre •C’est la moyenne des • C’est le plus grand
d'opérations qu'aura à complexités de l’algorithme nombre d’opérations
exécuter l'algorithme sur sur des jeux de données de qu’aura à exécuter
un jeu de données de taille n l’algorithme sur un jeu de
taille n. données de taille n
•Tmin(n) = mindDnT(d) •Tmoy(n) = ΣdDn T(d) / |Dn| •Tmax(n) = maxdDn T(d)
Notations:
Dn l’ensemble des données de taille n
T(n) le nombre d’opération sur un jeu donnée de taille n 10
NOTATION DE LANDAU
La notation de Landau « O » est celle qui est le
plus communément utilisée pour expliquer
formellement les performances d'un algorithme.
Cette notation exprime la limite supérieure d'une
fonction dans un facteur constant.
Exemple: T(n) = O(n2) veut dire qu'il existe une
constante c > 0 et une constante n0 > 0 tel que pour tout
11
n > n0 T(n) <= c n2
NOTATION DE LANDAU
Les règles de la notation O sont les suivantes :
Les termes constants : O(c) = O(1)
Les constantes multiplicatives sont omises :
O(cT ) = c O(T) = O(T)
L'addition est réalisée en prenant le maximum :
O(T1) + O(T2) = O(T1 + T2) = max(O(T1);O(T2))
La multiplication reste inchangée
O(T1)O(T2) = O(T1T2) 12
NOTATION DE LANDAU
Supposant que le temps d'exécution d’un algorithme est décrit par la fonction
T(n) = 3n2+10n+10, Calculer O(T(n))?
O(T(n)) = O(3 n2 + 10n + 10)
= O(max (3 n2, 10n, 10))
= O(3 n2)
= O (n2)
Remarque:
Pour n = 10 nous avons :
Temps d'exécution de 3 n2 : 3(10)2 / 3(10)2+10(10)+10 = 73,2%
Temps d'exécution de 10n : 10(10) / 3(10)2+10(10)+10 = 24,4%
Temps d'exécution de 10 : 10 / 3(10)2+10(10)+10 = 2,4%
Le poids de 3 n2 devient encore plus grand quand n = 100, soit 96,7%
On peut négliger les quantités 10n et 10.
13
Ceci explique les règles de la notation O.
CLASSES DE COMPLEXITÉ
Classe Notation O Exemple
Constante O(1) Accéder au premier élément d'un ensemble de données
Linéaire O(n) Parcourir un ensemble de données
Logarithmique O(log(n)) Couper un ensemble de données en deux parties égales,
puis couper ces moitiés en deux parties égales, etc.
Quasi-linéaire O(n log(n)) Couper répétitivement un ensemble de données en deux
et combiner les solutions partielles pour calculer la
solution générale
Quadratique O(n2) Parcourir un ensemble de données en utilisant deux
boucles imbriquées
Polynomiale O(nP) Parcourir un ensemble de données en utilisant P
boucles imbriquées
Exponentielle O(an) Générer tous les sous-ensembles possibles
d'un ensemble de données
14
CLASSES DE COMPLEXITÉ
15
CALCUL DE LA COMPLEXITÉ
1. Cas d'une instruction simple (écriture, lecture, affectation ) :
Le temps d'exécution de chaque instruction simple est O(1).
2. Cas d'une suite d'instructions simples: Le temps d ’exécution
d'une séquence d'instruction est déterminée par la règle de la
somme. C'est donc le temps de la séquence qui a le plus grand
temps d ’exécution: O(T) = O (T1 + T2) = max(O(T1);O(T2)) .
16
CALCUL DE LA COMPLEXITÉ
Exemple 2:
Permutation (Var S: tableau [0..n-1] d’entier, i, j: entier)
O(T1) = O(1)
tmpS[i]
O(T2) = O(1)
S[i]S[j]
O(T3) = O(1)
S[j]tmp
O(T) = O (T1 + T2 + T3) = O(1)
17
CALCUL DE LA COMPLEXITÉ
3. Cas d'un traitement conditionnel: Le temps d'exécution d'une
instruction SI est le temps d ’exécution des instructions exécutées
sous condition, plus le temps pour évaluer la condition. Pour une
alternative, on se place dans le cas le plus défavorable.
18
CALCUL DE LA COMPLEXITÉ
4. Cas d'un traitement itératif : Le temps d ’exécution d'une boucle
est la somme du temps pour évaluer le corps et du temps pour
évaluer la condition. Souvent ce temps est le produit du nombre
d'itérations de la boucle par le plus grand temps possible pour une
exécution du corps.
Boucle Pour Boule Tant que
19
CALCUL DE LA COMPLEXITÉ
Exemple 2:
Recherche séquentielle (S: tableau [0..n-1] d’entier, x: entier): booléen
i 0 c1
Trouve faux c2
Tant que ((i<n) et (non trouve)) faire Condition = c3;
DTQ nombre d’itération = n
Si (S[i] = x) alors c4
Trouve vrai c5
i i + 1 c6
FTQ
Retourner trouve c7
T(n) = c1+c2+n*(c3+c4+c5+c6) + c7 = c8 + c9 *n 20
O(T) = O(c8 + c9 *n) = O (n)
CALCUL DE LA COMPLEXITÉ
Exemple 3:
Tri par sélection (Var T: Tableau [1.. N] d’entier)
21
CALCUL DE LA COMPLEXITÉ
Exemple 4:
22
CALCUL DE LA COMPLEXITÉ
Exemple 5:
23
CALCUL DE LA COMPLEXITÉ
Exemple 6:
CALCUL DE LA COMPLEXITÉ
Exemple 7:
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
La complexité d’un algorithme récursif se fait par la
résolution d’une de ces équations de récurrence:
26
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 8: la fonction factorielle
Facto (n: entier): entier
Début
Si (n=1) alors retourner 1
Sinon retourner n*Facto (n-1);
Fin
27
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 8: la fonction factorielle
i.e. T(n) = T(n-1) + f(n) avec a = 1, T(0) = 0, f(n) = b;
28
O (T) = O (n)
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 9: T(n) = 2*T(n-1) + c avec T(0) = 0
O (T) = O(2n)
29
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 10: Recherche du maximum.
Fonction maximum ( Tab: Tableau , indDeb, indFin:entier)
Si ( indDeb = indFin) alors retourner (indDeb)
Sinon
M(indDeb+indFin) div 2 // division du problème en 2 sous-problèmes
k1 maximum (Tab, indDeb, m ) // régner sur le 1er sous-problème
k2 maximum (Tab, m+1, indFin) // régner sur le 2ème sous-problème
// Combiner les solutions
Si (Tab[k1] > Tab[k2]) alors retourner (k1) 30
Sinon retourner (k2)
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 10: Recherche du maximum.
T(n) = 2 T(n/2) + c
a = 2 , b = 2, k = 0 a > bk
T(n) = O(n) 31
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 11: Recherche dichotomique.
Fonction RechDicho(Tab :Tableau, borneinf, bornesup, x :entier) : bool
Si (borneinf<=bornesup) alors
mil (borneinf+bornesup) DIV 2 ;
Si (Tab[mil]=x) Alors retourner (vrai)
Sinon
Si (Tab[mil]>x) Alors
Retourner (RechDicho(Tab, borneinf, mil-1, x))
Sinon
Retourner(RechDicho(Tab, mil+1, bornesup, x))
Sinon
32
Retourner (Faux)
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 11: Recherche dichotomique
T(n) = T(n/2) + c
a = 1 , b = 2, k = 0 a = bk
T(n) = O(log(n))
33
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 12: Tri par Fusion
Tri_Fusion (T: tableau, debut, fin : entier)
Debut
Si (debut<fin) alors
milieu (debut + fin) /2
Tri_Fusion(T, debut, milieu);
Tri_fusion (T, milieu + 1, fin);
Interclasser (T, debut, milieu, fin)
FSI
Fin
34
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 12: Tri par Fusion
Procédure Interclasser(VAR T: tableau, debut, milieu, fin:
entier)
Debut
Tmp: tableau temporaire du taille fin-debut+1
i 0; i1 debut, i2 milieu + 1;
Tant que (i1≤milieu) et (i2 ≤ fin) faire
Si (T[i1]<T[i2]) alors Tmp[i]T[i1]; i1++;
Sinon Tmp [i]T[i2]; i2++;
i++;
Tant que (i1milieu) faire Tmp[i]T[i1]; i1++; i++;
Tant que (i2fin) faire Tmp[i]T[i2]; i2++; i++;
35
Pour idebut à fin faire T[i]=tmp[i-debut]; // recopier le tableau
Fin
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 12: Tri par Fusion
T(n) = 2 T(n/2) + n
a = 2 , b = 2, k = 1 a = bk
T(n) = O(n log n)
36
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 13 : La suite de Fibonacci
37
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Exemple 13 : La suite de Fibonacci
38
PARTIE II:
NP-COMPLÉTUDE
PLAN DE LA PARTIE II
Introduction (Vocabulaire Général)
Classification de Problème
Notion de Réduction
Théorie de NP-Complétude
Quelques Problèmes NP-Complets
40
INTRODUCTION
PROBLÈME DE DÉCISION
Pour des raisons de simplicité et techniques, la théorie de
la NP-Complétude se limite à l’étude des problèmes de
décision dont la solution est formulée en termes
oui/non.
Un problème de décision est une paire P =(X,Y), où
X est l’ensemble des instances de P ;
Y est l’ensemble des instances-«oui»
X \ Y est l’ensemble des instances-«non»
41
INTRODUCTION
PROBLÈME DE DÉCISION
Un algorithme pour un problème de décision (X,Y) est un
algorithme qui calcule la fonction F : X →{0, 1}, définie
par
Cette restriction aux problèmes de décision est justifiée
par le fait que les autres problèmes qui ne sont pas de
décision, comme les problèmes d’optimisation et de
recherche, peuvent être facilement transformés en un
42
problème de décision équivalent.
INTRODUCTION
PROBLÈME DE DÉCISION VS AUTRES PROBLÈMES
Problème de Recherche:
Exemple Entrée Réponse
Algorithme de recherche G (X, E) non Arbre recouvrant
(Trouver un arbre recouvrant) orienté
Algorithme de décision G (X, E) non Oui/Non
(Existence d’un arbre recouvrant) orienté
La réduction de la recherche à la décision est faite par test
d'hypothèse (La connexité de G)
43
INTRODUCTION
PROBLÈME DE DÉCISION VS AUTRES PROBLÈMES
Problème d’Optimisation:
Exemple Entrée Réponse
Algorithme d’optimisation G (X, E, L) Arbre
(Trouver un arbre recouvrant de poids non orienté recouvrant
minimum) minimum
Algorithme de décision G (X, E, L) Oui/Non
(Existence d’un arbre recouvrant de poids non orienté
k)
Lorsque le critère d'optimisation est borné a priori, la
réduction de l'optimisation à la décision est faite par test
d'hypothèse (La connexité de G et le poids de
44
l’arbre recouvrant).
INTRODUCTION
ALGORITHME DÉTERMINISTE VS NON-DÉTERMINISTE
Un algorithme déterministe est un algorithme dont la
solution qu’il produit peut être déduite des spécifications
de l’algorithme lui-même.
Un algorithme non déterministe est un algorithme dont
la solution est devinée puis vérifiée.
45
INTRODUCTION
ALGORITHME EFFICACE
Pour différentes raisons, la convention suivante s’est
imposée en informatique :
Un algorithme est efficace (ou facile) si sa complexité en
temps est polynomiale, c’est-à-dire en O(nk) pour un entier
k.
Un problème est de complexité polynomiale s'il existe un
46
algorithme de complexité polynomiale le résolvant.
CLASSIFICATION DES PROBLÈMES
CLASSE P
La classe P regroupe tous les problèmes de décision qui
peuvent être résolus par un algorithme déterministe de
complexité polynomiale.
Exemple:
Problème de l’existence de l’arbre de recouvrement de poids k
(Algorithme de Kruskal)
Problème de l’existence d’un chemin de longueur k (Algorithme
47
de Dijkstra)
CLASSIFICATION DES PROBLÈMES
CLASSE NP
La classe NP (Non deterministic Polynomial) regroupe
tous les problèmes de décision qui peuvent être résolus
par un algorithme non-déterministe de complexité
polynomiale (i.e. dont la solution peut être vérifiée en
temps polynomial)
Pour montrer qu’un problème est dans la classe
NP, il suffit de trouver un algorithme qui vérifie si une
solution donnée est valide en temps polynomiale.
48
CLASSIFICATION DES PROBLÈMES
CLASSE NP
Problème 1: Problème de Satisfaction en calcul
propositionnel (SAT)
Soit F = (x1, ...., xn) une formule du calcul propositionnel
en Forme Normale Conjonctive, i.e. F = C1 C2 ..... Cm
pour une collection de clauses {C1, C2, ....., Cm} sur l’
ensemble X = {x1, ...., xn } de variables booléennes
(littéraux).
Décider si F est satisfiable, c-à-d décider s’il existe x1, ....,
xn {0, 1}n tel que F s’évalue en vraie pour cette valeur 49
de
ses variables (toutes les clauses de C soient vraies).
CLASSIFICATION DES PROBLÈMES
CLASSE NP
Problème 2: Problème de K-SAT (k>2)
Soit F = (x1, ...., xn) une formule du calcul propositionnel
en Forme Normale Conjonctive, i.e. F = C1 C2 ..... Cm
pour une collection de clauses {C1, C2, ....., Cm} sur
l’ensemble X = {x1, ...., xn } tel que chaque clause
contient exactement k littéraux |Ci| = k.
Décider si F est satisfiable, c-à-d décider s’il existe x1, ....,
xn {0, 1}n tel que F s’évalue en vraie pour cette valeur de
50
ses variables (toutes les clauses de C soient vraies).
CLASSIFICATION DES PROBLÈMES
CLASSE NP
Problème 3: Problème de Coloriage de Graphe
Étant donnée le graphe G = (X, E) non orienté,
déterminer le nombre minimal de couleurs pour
colorier les sommets X du G tel que deux sommets
adjacent soient de couleur différente.
51
CLASSIFICATION DES PROBLÈMES
CLASSE NP
Problème 3: Problème de Coloriage de Graphe
Le problème de décision correspondant est:
Soient un graphe G = (X, E) et un entier k
Déterminer si le graphe G admet un coloriage avec au
moins k couleurs.
Ce problème de décision est connu sous le nom du
52 problème K-Coloriabilité
CLASSIFICATION DES PROBLÈMES
CLASSE NP
Problème 4: Problème du cycle hamiltonien
Soit G = (X, E) un graphe non orienté
Déterminer s’il existe un cycle hamiltonien, c’est-à-dire décider
s’il existe une chaîne de G passant une fois et une seule
par chacun des sommets et revenant à son point de départ.
Variantes: chaîne hamiltonien, circuit
hamiltonien, chemin hamiltonienne. 53
CLASSIFICATION DES PROBLÈMES
COMPARAISON ENTRE LES DEUX CLASSES P ET NP
Clairement, P NP mais la question qui se pose est :
P = NP ?
C’est l’une des questions (voire la question) non résolue les
plus célèbres qui défie les chercheurs depuis plus de 40 ans :
elle a été placée parmi la liste des sept problèmes du prix du
millénaire réputés insurmontables posés par le l’institut Clay
Mathematical en 2000. L’institut offre un million de dollars
à qui déterminerait la réponse à cette question. 54
CLASSIFICATION DES PROBLÈMES
COMPARAISON ENTRE LES DEUX CLASSES P ET NP
Clairement, P NP mais la question qui se pose est :
P = NP ?
Intérêt: Si P = NP, alors tous les problèmes vérifiables
polynomialement seraient décidables en temps polynomial.
La plupart des personnes pensent que ces deux classes sont
distinctes car il y a un très grand nombre de problèmes pour
lesquels on n’arrive pas à produire d’algorithme polynomiaux
depuis plus de 40 ans. 55
NOTION DE RÉDUCTION
IDÉE
Soient A et B deux problèmes. Si A se réduit à B (noté A
B) , alors
le problème A est plus facile que le problème B, ou
le problème B est plus difficile que le problème A.
56
NOTION DE RÉDUCTION
DÉFINITION
Soient A (XA, YA) et B (XB, YB) deux problèmes de
décision. Une réduction de A vers B (A B) est une
fonction R : XA XB calculable en temps polynomial telle
que
aYA ssi R(a) YB :
57
NOTION DE RÉDUCTION
PROPRIÉTÉS
Soient A (XA, YA), B (XB, YB) et C (XC, YC) des problèmes
de décision.
A ≤A Réflexive
A ≤B et B ≤C impliquent A ≤C. Transitive
A ≤B et B ≤A impliquent A ≡B (A et B sont
équivalents). Anti-symétrique
58
NOTION DE RÉDUCTION
APPLICATION À LA COMPARAISON DE DIFFICULTÉ
Intuitivement, si un problème est plus facile qu’un
problème polynomial, alors il est polynomial.
Formellement :
Si A B, et si B P alors A P.
Si A B, et si A P alors B P.
59
THÉORIE NP-COMPLÉTUDE
DÉFINITION
Un problème B est dit NP-complet, si
1. B NP
2. A NP, A B.
Les problèmes NP-complets sont donc les plus difficiles de
la classe NP.
60
THÉORIE NP-COMPLÉTUDE
PREUVE
Pour prouver la NP-complétude d’un problème B, il suffit
de prouver que :
1. B est dans NP;
2. A B pour un problème A que l’on sait déjà NP-
complet.
La difficulté est d’arriver à en produire un premier
61
problème NP-Complet.
THÉORIE NP-COMPLÉTUDE
PROBLÈME 1: SAT
Théorème 1 (Cook-Levin, 1971): Le problème SAT est
NP-complet.
Le problème SAT est le premier problème montré comme
NP-complet.
Résultat admis: la preuve consiste en un codage d'une
machine de Turing qui vérifie les solutions du problème
en temps polynomial.
Ce théorème va être utilisé pour en montrer par réduction
62
d’autres problèmes NP-Complet.
THÉORIE NP-COMPLÉTUDE
PROBLÈME 2: 3-SAT
Théorème 2 (Cook-Levin, 1971): Le problème de 3-
SAT est NP-Complet.
Preuve 2: Il faut montrer que :
1. 3-SAT est dans NP;
2. SAT 3-SAT (réduire SAT à 3-SAT).
F3-sat Oui
Fsat R est elle
satisfiable?
F3-sat
63
Non
THÉORIE NP-COMPLÉTUDE
PREUVE 2 : LE PROBLÈME DE DE 3-SAT EST NP-COMPLET
Preuve 2: SAT 3-SAT (réduire SAT à 3-SAT).
Toute clause du problème SAT peut être remplacée de manière
équivalente par un ensemble de clauses 3-SAT qui contiennent
chacune exactement trois littéraux.
64
THÉORIE NP-COMPLÉTUDE
PREUVE 2 : LE PROBLÈME DE DE 3-SAT EST NP-COMPLET
Preuve 2: SAT 3-SAT (réduire SAT à 3-SAT).
Toute clause du problème SAT peut être remplacée de manière
équivalente par un ensemble de clauses 3-SAT qui contiennent
chacune exactement trois littéraux.
65
THÉORIE NP-COMPLÉTUDE
PREUVE 2 : LE PROBLÈME DE DE 3-SAT EST NP-COMPLET
Preuve 2: SAT 3-SAT (réduire SAT à 3-SAT).
La satisfiabilité des clauses Z’ est donc équivalente à la
satisfaisabilité de l’ensemble initiale Z.
La réduction est manifestement polynomiale ; on a donc bien prouvé
que SAT se réduisait à 3-SAT; ce dernier est donc bien NP-complet
66
THÉORIE NP-COMPLÉTUDE
PROBLÈME 3: 3-COLORIABLE
Théorème 3: Le problème de 3-Coloriable est NP-
Complet.
Preuve 3: Il faut montrer que :
1. 3-Coloriable est dans NP;
2. 3-SAT 3-Coloriable (réduire 3-SAT à 3-Coloriable).
G
est il 3- Oui
F3-sat R Coloriable
G = (V, E) ?
67
Non
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
On construit un graphe ayant 3 + 2 n + 5 m sommets tels que:
1. Les trois premiers sont notés VRAI, FAUX, NSP. Ces trois sommets
sont reliés deux à deux en triangle, de sorte qu’ils doivent être tous
trois de couleurs différentes. On appellera les couleurs
correspondantes CVRAI(e.g. vert), CFAUX(e.g. rouge), CNSP (e.g. bleu)
NSP
68
VRAI FAUX
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
On construit un graphe ayant 3 + 2 n + 5 m sommets tels que:
2. On associe un sommet à chaque variable (Xi) et au complémentaire
de chaque variable (Not Xi). Pour assurer qu’une variable prenne la
valeur VRAI ou FAUX, on construit un triangle dont les sommets
sont Xi, NOT Xi, et NSP.
NSP NSP
Not Not 69
Xi Xi
Xi Xi
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
On construit un graphe ayant 3 + 2 n + 5 m sommets tels que:
3. Pour chaque clause {A, B, C}, on introduit le motif :
A 3
2
0
B 4
VRAI
C 1
Ce motif est 3-coloriable 70
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
On construit un graphe ayant 3 + 2 n + 5 m sommets tels que:
Ce motif est 3-coloriable A 3
2
0
B 4
VRAI
CVRAI ou CFAUX C 1
A 3
2
0
B 4 71
VRAI
CVRAI ou CFAUX C 1
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
On construit un graphe ayant 3 + 2 n + 5 m sommets tels que:
Ce motif est 3-coloriable A 3
2
0
CVRAI ou CFAUX B 4
VRAI
C 1
CVRAI ou CFAUX A 3
2
0
B 4
VRAI 72
C 1
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
Considérons alors le graphe formé des trois sommets distingués, des
triangles formés sur les variables, et des motifs donnés. Si ce graphe
est 3-coloriable, alors en particulier tout sous-graphe est coloriable.
À partir d’une 3-coloration du graphe, on construit une affectation de
valeurs de vérité en mettant à 1 toutes les variables coloriées par
CVRAI. Cette affectation est cohérente (une variable et son
complémentaire ont bien une valeur opposée) et au moins une
variable par clause est à 1.
Inversement, étant donné une affectation de valeurs de vérité, il est
73
aisé de déduire une 3-coloration du graphe.
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
Exercice: Soit F =
1. Donner le graphe qui représente ces clauses et
déduire une affectation de valeurs de vérité qui
satisfait F.
2. Montrer que le graphe est 3-coloriable pour
l’affectation de valeurs de vérité suivante (x1, x2, x3)
= (0, 0, 0).
74
THÉORIE NP-COMPLÉTUDE
PREUVE 3 : LE PROBLÈME DE 3-COLORIABLE EST NP-COMPLET
Preuve 3: 3-SAT 3-Coloriable.
L’existence d’une 3-coloration du graphe est donc
équivalente à la satisfaisabilité de la formule initiale.
La réduction est manifestement polynomiale ; on a donc
bien prouvé que 3-SAT se réduisait à 3-COLORABILITE ;
ce dernier est donc bien NP-complet.
75
THÉORIE NP-COMPLÉTUDE
PROBLÈME 4: CYCLE HAMILTONIEN
Théorème 4 (Karp, 1972): Le problème de Cycle
Hamiltonien est NP-Complet.
Preuve 4: Il faut montrer que :
1. Cycle Hamiltonien est dans NP;
2. Plusieurs méthodes:
a. 3-SAT Cycle Hamiltonien.
b. 3-SAT Recouvrement de Sommets Cycle Hamiltonien
76
c. 3-SAT Stable Recouvrement de Sommets Cycle
hamiltonien
THÉORIE NP-COMPLÉTUDE
PREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET
Preuve 4 (Papadimitriou et Steiglitz, 1982) :
3-SAT Cycle Hamiltonien.
G Oui
F3-sat R contient il
G = (V, E) un C. H?
Non
77
THÉORIE NP-COMPLÉTUDE
PREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET
Preuve 4 (Papadimitriou et Steiglitz, 1982) :
On construit le graphe de la manière suivante:
1. Pour chaque variable, on introduit le sous graphe suivant:
X
Not X
2. Chaque nouvelle variable est liée à la précédente
X1 X2 Xn
78
THÉORIE NP-COMPLÉTUDE
PREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET
Preuve 4 (Papadimitriou et Steiglitz, 1982) :
On construit le graphe de la manière suivante:
3. Pour chaque clause, on introduit la structure B :
Aucun cycle hamiltonien de
G ne peut traverser à la fois
L1, L2 et L3.
U' L3 L2 L1 U
79
THÉORIE NP-COMPLÉTUDE
PREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET
Preuve 4 (Papadimitriou et Steiglitz, 1982) :
On construit le graphe de la manière suivante:
4. Les clauses sont liées comme suit:
C1 C2 Cm
X1 X2 Xn
80
THÉORIE NP-COMPLÉTUDE
PREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET
Preuve 4 (Papadimitriou et Steiglitz, 1982) :
On construit le graphe de la manière suivante:
5. Les littéraux de chaque clause sont liés aux variables par la
structure A comme suit:
81
THÉORIE NP-COMPLÉTUDE
PREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET
Preuve 4 (Papadimitriou et Steiglitz, 1982) :
Par exemple, le graphe suivant présente ces clauses
C1 C2 C3
A A
A A
A A A
A
A 82
X1 X2 X3
THÉORIE NP-COMPLÉTUDE
PREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET
Preuve 4 (Papadimitriou et Steiglitz, 1982) :
Nous affirmons maintenant que G est hamiltonien si et seulement si
F3-sat est satisfaisable. Soit C un cycle hamiltonien. On définit un
assignement en fixant un littéral à vrai si et seulement si C contient
l’arête correspondante. D’après les propriétés des structures A et B,
chaque clause contient un littéral qui est vrai.
Inversement, tout assignement satisfaisant définit un ensemble
d’arêtes qui correspondent à des littéraux qui sont vrai. Comme
chaque clause contient un littéral qui est vrai, cet ensemble d’arêtes
peut être complété en un cycle hamiltonien de G. 83
Enfin, la réduction est trivialement polynomiale.
SOURCES DE CE COURS
Frédéric Vivien, Algorithmique avancée, École Normale Supérieure de Lyon, 2002.,
pp. 93. Disponible sur [Link]
2001-2002/[Link]
Slim Msfar, Algorithmique et Complexité, 2012, pp 104. Disponible sur
[Link]
Djamel-Eddine ZEGOUR, O-Notation, École nationale Supérieure d’Informatique, pp
33. Disponible sur
[Link]
Olivier Bournez, Fondements de l’informatique Logique, modèles, et calculs, Chapitre
12: Quelques problèmes NP-complets, Cours INF423 de l’Ecole Polytechnique, 2013,
pp. 234.
Jean Fonlupt et Alexandre Skoda. Optimisation combinatoire – Théorie et
algorithmes, Chapitre 15: NP-complétude, 2010, 664p.
Gilles Schaeffer, Cours 4: Réduction et NP-complétude, 2010, pp. 124, Disponible sur
[Link]
[Link]
Johanne Cohen, La NP-complétude, PRISM/CNRS, 2012, pp. 95, Disponible sur
[Link] 84
