Chapitre 3 NP-complétude

CHAPITRE III: NP-COMPLÉTUDE

Université Blida 1Faculté des Sciences

Département d’InformatiqueMaster GSI (Génie des Systèmes Informatiques)

Semestre 1

Mme AROUSSI

2015-2016

Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/

PARTIE I:RAPPEL SUR LA COMPLEXITÉ

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

PLAN DE LA PARTIE I

4

Le temps d’exécution d’un algorithme dépend des facteurssuivants :

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 algorithmeindépendamment de la machine et du langage utilisés, c.-à-d. uniquement en fonction de la taille des données quel’algorithme doit traiter.

INTRODUCTION

5

INTRODUCTIONEXEMPLE: 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,

X:entier): entier.

6

2ème variante Début Inter1 P 0 Pour 0 à n faire P P+ Inter *T[i] Inter Inter * X

FP Fin

1ère variante Début P0 Pour i 0 à n faire P P+ T[i] * Puiss (X, i)

FP Fin

1ère Complexité : 1ère Complexité : (n+1) additions

(n+1) multiplications(n+1) puissances

Au moins 3 variables

2ème Complexité : (n+1) additions

2(n+1) multiplications3 variables


7

3ème variante: Schéma de HornerP(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] Pour i n-1 à 0 faire P P*X + T[i]

FP Fin

3ème Complexité : n additions

n multiplications2 variables


8

Variantes Première Deuxième Troisième Complexité en temps(en terme de nombre d’opérations)

(n+1) additions(n+1) multiplications(n+1) puissances

(n+1) additions 2(n+1) multiplications

n additions n multiplications

Complexitéen espace mémoire (Variables)

P, i et les variables de la fonction puissance appelée (n+1) fois

P, i et Inter P, i

Nécessité d’estimer la complexité en temps et enespace d’un algorithme avant de l’écrire etl’implémenter


9

La complexité (temporelle) d’un algorithme est lamesure du nombre d’opérations fondamentales(affectations, comparaisons, opérations arithmétiques)qu’il effectue sur un jeu de données. Elle est expriméecomme 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 siun algorithme A et meilleur qu’un algorithme Bindépendamment de la machine, du langage de programmation,du compilateur et des détails d’implémentation.

DÉFINITION

10

TYPE DE LA COMPLEXITÉ

Complexité au meilleur

•C'est le plus petit nombred'opérations qu'aura àexécuter l'algorithme surun jeu de données detaille n.

•Tmin(n) = mindDnT(d)

Complexité en moyenne

•C’est la moyenne descomplexités de l’algorithmesur des jeux de données detaille n

•Tmoy(n) = ΣdDn T(d) / |Dn|

Complexité au pire

• C’est le plus grandnombre d’opérationsqu’aura à exécuterl’algorithme sur un jeu dedonnées de taille n

•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

11

Exemple: T(n) = O(n2) veut dire qu'il existe uneconstante c > 0 et une constante n0 > 0 tel que pour toutn > n0 T(n) <= c n2

La notation de Landau « O » est celle qui est leplus communément utilisée pour expliquerformellement les performances d'un algorithme.

NOTATION DE LANDAU

Cette notation exprime la limite supérieure d'unefonction dans un facteur constant.

12

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)

NOTATION DE LANDAU

13

Supposant que le temps d'exécution d’un algorithme est décrit par la fonctionT(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.

Ceci explique les règles de la notation O.

NOTATION DE LANDAU

14

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 lasolution 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

15

CLASSES DE COMPLEXITÉ

16

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écutiond'une séquence d'instruction est déterminée par la règle de lasomme. C'est donc le temps de la séquence qui a le plus grandtemps d ’exécution: O(T) = O (T1 + T2) = max(O(T1);O(T2)) .

17


Exemple 2:

Permutation (Var S: tableau [0..n-1] d’entier, i, j: entier)

O(T) = O (T1 + T2 + T3) = O(1)

tmpS[i] O(T1) = O(1)

S[i]S[j] O(T2) = O(1)

S[j]tmp O(T3) = O(1)

18


3. Cas d'un traitement conditionnel: Le temps d'exécution d'uneinstruction SI est le temps d ’exécution des instructions exécutéessous condition, plus le temps pour évaluer la condition. Pour unealternative, on se place dans le cas le plus défavorable.

19


4. Cas d'un traitement itératif : Le temps d ’exécution d'une boucleest la somme du temps pour évaluer le corps et du temps pourévaluer la condition. Souvent ce temps est le produit du nombred'itérations de la boucle par le plus grand temps possible pour uneexécution du corps.

Boucle Pour Boule Tant que

20


Exemple 2:Recherche séquentielle (S: tableau [0..n-1] d’entier, x: entier): booléen

i 0 c1Trouve faux c2Tant que ((i<n) et (non trouve)) faire Condition = c3;

nombre d’itération = nDTQSi (S[i] = x) alors c4

Trouve vrai c5i i + 1 c6

FTQRetourner trouve c7

T(n) = c1+c2+n*(c3+c4+c5+c6) + c7 = c8 + c9 *n

O(T) = O(c8 + c9 *n) = O (n)

21


Exemple 3:

Tri par sélection (Var T: Tableau [1.. N] d’entier)

22


Exemple 4:

23


Exemple 5:


Exemple 6:


Exemple 7:

26

La complexité d’un algorithme récursif se fait par larésolution d’une de ces équations de récurrence:

COMPLEXITÉ DES ALGORITHMES RÉCURSIFS

27

Exemple 8: la fonction factorielleFacto (n: entier): entierDébutSi (n=1) alors retourner 1 Sinon retourner n*Facto (n-1); Fin


28

Exemple 8: la fonction factorielle

i.e. T(n) = T(n-1) + f(n) avec a = 1, T(0) = 0, f(n) = b;

O (T) = O (n)


29

Exemple 9: T(n) = 2*T(n-1) + c avec T(0) = 0

O (T) = O(2n)


30

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

k1maximum (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)

Sinon retourner (k2)

31

Exemple 10: Recherche du maximum.T(n) = 2 T(n/2) + c

a = 2 , b = 2, k = 0 a > bk

T(n) = O(n)


32

Fonction RechDicho(Tab :Tableau, borneinf, bornesup, x :entier) : boolSi (borneinf<=bornesup) alors

mil (borneinf+bornesup) DIV 2 ;Si (Tab[mil]=x) Alors retourner (vrai)Sinon

Si (Tab[mil]>x) AlorsRetourner (RechDicho(Tab, borneinf, mil-1, x))

SinonRetourner(RechDicho(Tab, mil+1, bornesup, x))

SinonRetourner (Faux)

Exemple 11: Recherche dichotomique.


33

Exemple 11: Recherche dichotomiqueT(n) = T(n/2) + c

a = 1 , b = 2, k = 0 a = bk

T(n) = O(log(n))


34

Exemple 12: Tri par Fusion


Tri_Fusion (T: tableau, debut, fin : entier)DebutSi (debut<fin) alors

milieu (debut + fin) /2Tri_Fusion(T, debut, milieu);Tri_fusion (T, milieu + 1, fin);Interclasser (T, debut, milieu, fin)

FSIFin

35

Procédure Interclasser(VAR T: tableau, debut, milieu, fin:entier)

DebutTmp: tableau temporaire du taille fin-debut+1i0; 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++;Pour idebut à fin faire T[i]=tmp[i-debut]; // recopier le tableauFin


Exemple 12: Tri par Fusion

36

Exemple 12: Tri par FusionT(n) = 2 T(n/2) + n

a = 2 , b = 2, k = 1 a = bk

T(n) = O(n log n)


37

Exemple 13 : La suite de Fibonacci


38

Exemple 13 : La suite de Fibonacci


PARTIE II:NP-COMPLÉTUDE

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

PLAN DE LA PARTIE II

41

Pour des raisons de simplicité et techniques, la théorie dela NP-Complétude se limite à l’étude des problèmes dedécision dont la solution est formulée en termesoui/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»

INTRODUCTIONPROBLÈME DE DÉCISION

42

Un algorithme pour un problème de décision (X,Y) est unalgorithme qui calcule la fonction F : X →{0, 1}, définiepar

Cette restriction aux problèmes de décision est justifiéepar le fait que les autres problèmes qui ne sont pas dedécision, comme les problèmes d’optimisation et derecherche, peuvent être facilement transformés en unproblème de décision équivalent.

INTRODUCTIONPROBLÈME DE DÉCISION

43

Problème de Recherche:

La réduction de la recherche à la décision est faite par test d'hypothèse (La connexité de G)

INTRODUCTIONPROBLÈME DE DÉCISION VS AUTRES PROBLÈMES

Exemple Entrée RéponseAlgorithme de recherche(Trouver un arbre recouvrant)

G (X, E) non orienté

Arbre recouvrant

Algorithme de décision(Existence d’un arbre recouvrant)

G (X, E) non orienté

Oui/Non

44

Problème d’Optimisation:

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 l’arbre recouvrant).

INTRODUCTIONPROBLÈME DE DÉCISION VS AUTRES PROBLÈMES

Exemple Entrée RéponseAlgorithme d’optimisation(Trouver un arbre recouvrant de poids minimum)

G (X, E, L) non orienté

Arbre recouvrant minimum

Algorithme de décision(Existence d’un arbre recouvrant de poids k)

G (X, E, L) non orienté

Oui/Non

45

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.

INTRODUCTIONALGORITHME DÉTERMINISTE VS NON-DÉTERMINISTE

46

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

algorithme de complexité polynomiale le résolvant.

INTRODUCTIONALGORITHME EFFICACE

47

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

de Dijkstra)

CLASSIFICATION DES PROBLÈMESCLASSE P

48

La classe NP (Non deterministic Polynomial) regroupetous les problèmes de décision qui peuvent être résoluspar 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 classeNP, il suffit de trouver un algorithme qui vérifie si unesolution donnée est valide en temps polynomiale.

CLASSIFICATION DES PROBLÈMESCLASSE NP

49

Problème 1: Problème de Satisfaction en calculpropositionnel (SAT)

Soit F = (x1, ...., xn) une formule du calcul propositionnelen 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 deses variables (toutes les clauses de C soient vraies).


50

Problème 2: Problème de K-SAT (k>2)

Soit F = (x1, ...., xn) une formule du calcul propositionnelen Forme Normale Conjonctive, i.e. F = C1 C2 ..... Cm

pour une collection de clauses {C1, C2, ....., Cm} surl’ensemble X = {x1, ...., xn } tel que chaque clausecontient 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 deses variables (toutes les clauses de C soient vraies).


51

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.


52

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 de k couleurs.

Ce problème de décision est connu sous le nom du

problème K-Coloriabilité


53

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 un chaîne de G passant une fois et une seule par

chacun des sommet et revenant à son point de départ.

Variantes: chaîne hamiltonien, circuit

hamiltonien, chemin hamiltonienne.


54

Clairement, P NP mais la question qui se pose est :

P = NP ?

C’est l’une des questions (voire la question) non résolue lesplus 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.

CLASSIFICATION DES PROBLÈMESCOMPARAISON ENTRE LES DEUX CLASSES P ET NP

55

Clairement, P NP mais la question qui se pose est :

P = NP ?

Intérêt: Si P = NP, alors tous les problèmes vérifiablespolynomialement seraient décidables en temps polynomial.

La plupart des personnes pensent que ces deux classes sontdistinctes car il y a un très grand nombre de problèmes pourlesquels on n’arrive pas à produire d’algorithme polynomiauxdepuis plus de 40 ans.

CLASSIFICATION DES PROBLÈMESCOMPARAISON ENTRE LES DEUX CLASSES P ET NP

56

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.

NOTION DE RÉDUCTIONIDÉE

57

Soient A (XA, YA) et B (XB, YB) deux problèmes dedécision. Une réduction de A vers B (A B) est unefonction R : XA XB calculable en temps polynomial telleque

aYA ssi R(a) YB :

NOTION DE RÉDUCTIONDÉFINITION

R

58

Soient A (XA, YA), B (XB, YB) et C (XC, YC) des problèmes

de décision.

A A

A B et B C impliquent A C.

A B et B A impliquent A B (A et B sont

équivalents).

NOTION DE RÉDUCTIONPROPRIÉTÉS

59

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.

NOTION DE RÉDUCTIONAPPLICATION À LA COMPARAISON DE DIFFICULTÉ

60

THÉORIE NP-COMPLÉTUDEDÉ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 dela classe NP.

61

THÉORIE NP-COMPLÉTUDEPREUVE

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

problème NP-Complet.

62

THÉORIE NP-COMPLÉTUDEPROBLÈME 1: SAT

Théorème 1 (Cook-Levin, 1971): Le problème SAT estNP-complet.

Le problème SAT est le premier problème montré commeNP-complet.

Résultat admis: la preuve consiste en un codage d'unemachine de Turing qui vérifie les solutions du problèmeen temps polynomial.

Ce théorème va être utilisé pour en montrer par réductiond’autres problèmes NP-Complet.

63

THÉORIE NP-COMPLÉTUDEPROBLÈ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).

RF3-sat

est elle satisfiable?

FsatF3-sat

Non

Oui

64

THÉORIE NP-COMPLÉTUDEPREUVE 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 contiennentchacune exactement trois littéraux.

65


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 contiennentchacune exactement trois littéraux.

66


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

67

THÉORIE NP-COMPLÉTUDEPROBLÈME 3: 3-COLORIABLE

Théorème 3: Le problème de 3-Coloriable est NP-

Complet.


1. 3-Coloriable est dans NP;

2. 3-SAT 3-Coloriable (réduire 3-SAT à 3-Coloriable).

RG

est il 3-Coloriable

?F3-sat

G = (V, E)

Non

Oui

68

THÉORIE NP-COMPLÉTUDEPREUVE 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 sommetssont reliés deux à deux en triangle, de sorte qu’ils doivent être toustrois de couleurs différentes. On appellera les couleurscorrespondantes CVRAI(e.g. vert), CFAUX(e.g. rouge), CNSP (e.g. bleu)

NSP

VRAI FAUX

69


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émentairede chaque variable (Not Xi). Pour assurer qu’une variable prenne lavaleur VRAI ou FAUX, on construit un triangle dont les sommetssont Xi, NOT Xi, et NSP.

NSP

Xi Not Xi

NSP

Xi Not Xi

70




3. Pour chaque clause {A, B, C}, on introduit le motif :

Ce motif est 3-coloriable

A

B

C

3

4

2 0

1

VRAI

71

A

B

C

3

4

2 0

1

VRAI

CVRAI ou CFAUX

A

B

C

3

4

2 0

1

VRAI

CVRAI ou CFAUX

Preuve 3: 3-SAT 3-Coloriable.On construit un graphe ayant 3 + 2 n + 5 m sommets tels que:



72





A

B

C

3

4

2 0

1

VRAI

CVRAI ou CFAUX

A

B

C

3

4

2 0

1

VRAICVRAI ou CFAUX

73



Considérons alors le graphe formé des trois sommets distingués, destriangles formés sur les variables, et des motifs donnés. Si ce grapheest 3-coloriable, alors en particulier tout sous-graphe est coloriable.

À partir d’une 3-coloration du graphe, on construit une affectation devaleurs de vérité en mettant à 1 toutes les variables coloriées parCVRAI. Cette affectation est cohérente (une variable et soncomplémentaire ont bien une valeur opposée) et au moins unevariable par clause est à 1.

Inversement, étant donné une affectation de valeurs de vérité, il estaisé de déduire une 3-coloration du graphe.

74


Exercice: Soit F =

1. Donner le graphe qui représente ces clauses etdéduire une affectation de valeurs de vérité quisatisfait F.

2. Montrer que le graphe est 3-coloriable pourl’affectation de valeurs de vérité suivante (x1, x2, x3)= (0, 0, 0).


75



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.

76

THÉORIE NP-COMPLÉTUDEPROBLÈME 4: CYCLE HAMILTONIEN

Théorème 4 (Karp, 1972): Le problème de Cycle

Hamiltonien est NP-Complet.


1. Cycle Hamiltonien est dans NP;

2. Plusieurs méthodes:a. 3-SAT Cycle Hamiltonien.

b. 3-SAT Recouvrement de Sommets Cycle Hamiltonien

c. 3-SAT Stable Recouvrement de Sommets Cyclehamiltonien

77

THÉORIE NP-COMPLÉTUDEPREUVE 4 : LE PROBLÈME DE CYCLE HAMILTONIEN EST NP-COMPLET

Preuve 4 (Papadimitriou et Steiglitz, 1982) :

3-SAT Cycle Hamiltonien.

RG

contient il un C. H?

F3-satG = (V, E)

Non

Oui

78



On construit le graphe de la manière suivante: 1. Pour chaque variable, on introduit le sous graphe suivant:

2. Chaque nouvelle variable est liée à la précédente

X

Not X

X1 X2 Xn

79



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.

UU' L1L2L3

80



On construit le graphe de la manière suivante: 4. Les clauses sont liées comme suit:

C1 C2 Cm

X1 X2 Xn

81



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:

82



Par exemple, le graphe suivant présente ces clauses

C1 C2 C3

X1 X2 X3

A AA

A

AA

AA A

83



Nous affirmons maintenant que G est hamiltonien si et seulement siF3-sat est satisfaisable. Soit C un cycle hamiltonien. On définit unassignement en fixant un littéral à vrai si et seulement si C contientl’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 ensembled’arêtes qui correspondent à des littéraux qui sont vrai. Commechaque clause contient un littéral qui est vrai, cet ensemble d’arêtespeut être complété en un cycle hamiltonien de G.

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 http://perso.ens-lyon.fr/frederic.vivien/Enseignement/Algo-2001-2002/Cours.pdf

Slim Msfar, Algorithmique et Complexité, 2012, pp 104. Disponible surhttp://p835.phpnet.org/testremorque/upload/catalogue/coursalgorithmi.pdf

Djamel-Eddine ZEGOUR, O-Notation, École nationale Supérieure d’Informatique, pp33. Disponible surhttp://www.zegour.netii.net/Site%20secondaire/Mcp/Cours%20ppt/1_o-notation.pdf

Olivier Bournez, Fondements de l’informatique Logique, modèles, et calculs, Chapitre12: Quelques problèmes NP-complets, Cours INF423 de l’Ecole Polytechnique, 2013,pp. 234.

Jean Fonlupt et Alexandre Skoda. Optimisation combinatoire – Théorie etalgorithmes, Chapitre 15: NP-complétude, 2010, 664p.

Gilles Schaeffer, Cours 4: Réduction et NP-complétude, 2010, pp. 124, Disponible surhttp://www.enseignement.polytechnique.fr/informatique/INF550/Cours1011/INF550-2010-5.pdf

Johanne Cohen, La NP-complétude, PRISM/CNRS, 2012, pp. 95, Disponible surhttp://www.prism.uvsq.fr/~joco/enseignement/Complexite.pdf 84

Education

Chapitre 3 NP-complétude