Chapitre 6 : NP-compl´etude
Alexandre Blondin Mass´e
Laboratoire d’informatique formelle
Universit´
e du Qu´
ebec `
a Chicoutimi
10 f´evrier 2014
Cours 8INF870
D´epartement d’informatique et math´ematique
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
1 / 43
Table des mati`eres
1. Les classes de complexit´e
2. La classe NP
3. Probl`emes NP-complets
4. R´eductions
5. Strat´egies de r´esolution
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
2 / 43
Algorithme polynomial
I
Soit A un algorithme ;
I
Soit T (n) le temps d’ex´
ecution de A ;
I
On dit que A est polynomial s’il existe un polynˆ
ome
p(n) tel que T (n) est O(p(n)) ;
I
Bref, A est polynomial s’il s’ex´ecute en temps
polynomial.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
4 / 43
Probl`eme de d´ecision
I
Soit I un ensemble d’objets (liste, arbres, graphes, etc.)
I
Soit J ⊆ I ;
I
On appelle probl`
eme de d´
ecision le probl`eme qui
consiste `a d´ecider si un objet x ∈ I se trouve dans J .
I
Exemple :
I
I est l’ensemble de tous les graphes non orient´
es ;
I
J est l’ensemble des graphe non orient´es qui sont
eul´
eriens, c’est-`
a-dire qui admettent un cycle passant
exactement une fois par chaque arˆete ;
I
Le probl`eme de d´ecision associ´e est not´e EULD.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
5 / 43
Cycles hamiltoniens
I
´
Etant
donn´e un graphe non orient´
e G, est-ce que G est
hamiltonien ?
I
Autrement dit, existe-t-il dans G un cycle passant par
chaque sommet exactement une fois ?
I
Ce probl`eme de d´
ecision est d´enot´e HAMD.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
6 / 43
Probl`eme du commis-voyageur
I
Soit n un entier positif et N = {1, 2, . . . , n} ;
I
Soit Kn le graphe complet, dont l’ensemble des sommets
est N ;
I
Soit w : P2 (N ) → R une fonction de poids sur les arˆ
etes
de Kn ;
I
Le probl`eme de trouver un cycle hamiltonien de Kn de
poids minimal n’est pas un probl`eme de d´ecision ;
I
Le probl`eme de d´
ecider si Kn admet un cycle hamiltonien
de poids plus petit qu’un nombre r´eel k fix´e est un
probl`
eme de d´
ecision ;
I
Il est not´e k-TSPD.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
7 / 43
Couverture des arˆetes par les sommets
I
Soit G = (V, E) un graphe non orient´
e sans sommet isol´e
et un entier k ;
I
On aimerait d´eterminer s’il existe un sous-ensemble de
sommets V 0 ⊆ V , avec |V 0 | ≤ k, tel que
si {u, v} ∈ E, alors u ∈ V 0 ou v ∈ V 0 .
I
Autrement dit, V 0 couvre toutes les arˆ
etes de G ;
I
On d´enote ce probl`eme par k-VCD (vertex cover).
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
8 / 43
Test de primalit´e
I
Soit n un nombre naturel de k bits ;
I
On d´enote par PRIMED le probl`eme de d´
ecider si n est
premier ou non ;
I
Le test na¨ıf consiste `
a tester si n est divisible par un
√
√
nombre entre 2 et n, dont la complexit´e est O( n) ;
I
Comme k = dlog2 ne, on en d´eduit n = 2k ;
I
√ k
La complexit´e en fonction de k est alors O( 2 ), qui est
exponentiel.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
9 / 43
La classe P
I
L’ensemble de tous les probl`emes de d´
ecision pouvant ˆetre
r´esolus en temps polynomial est d´enot´ee par P ;
I
Exemple :
I
I
Indiquer si un tableau est tri´e se fait en temps O(n)
et donc le probl`eme est dans P ;
I
D´eterminer s’il existe un chemin de longueur au
plus k entre deux sommets u et v se fait en temps
O(nm) (algorithme de Bell-Ford) et est donc dans P ;
I
D´eterminer si une matrice carr´ee d’ordre n est
inversible se fait en temps O(n3 ), qui est aussi
polynomial ;
Qu’en est-il de PRIMED ? EULD ? HAMD ? VCD ?
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
10 / 43
Algorithme de v´erification
I
Soit I et J ⊆ I ;
I
´
Etant
donn´e x ∈ I, consid´erons le probl`eme de d´
ecision
qui consiste `a d´eterminer si x ∈ J ;
I
Supposons qu’il existe un algorithme A ayant la propri´et´e
que pour toute instance x ∈ I, il existe un certificat c tel
que
x∈J
I
si et seulement si
A(x, c) retourne vrai.
L’algorithme A est appel´e algorithme de v´
erification.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
12 / 43
Exemple
I
Reprenons l’exemple du probl`eme HAMD ;
I
Il est difficile de trouver un cycle hamiltonien dans un
graphe ;
I
En revanche, supposons qu’on vous donne une
permutation des sommets du graphe (le certificat) ;
I
Alors il est possible de v´erifier en temps lin´
eaire (et donc
polynomial) que la suite en question forme bien un cycle
hamiltonien ;
I
Ce dernier algorithme est un exemple d’algorithme de
v´
erification.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
13 / 43
La classe NP
I
Consid´erons un probl`eme de d´
ecision pour lequel un
algorithme de v´
erification A existe ;
I
Supposons que A s’ex´ecute en temps polynomial ;
I
Supposons en outre que tous les certificats associ´es `a une
instance utilisent un espace polynomial ;
I
Alors on dit que le probl`eme en question est dans la classe
NP ;
I
Attention ! NP 6= non polynomial.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
14 / 43
Probl`emes NP
Est-ce que les probl`emes suivants sont de classe NP ?
I
EULD ?
I
HAMD ?
I
VCD ?
I
PRIMED ?
Th´eor`eme
Tout probl`eme de classe P est dans la classe NP. Plus
simplement,
P ⊆ NP.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
15 / 43
Conjecture P 6= NP
I
Un des plus grands probl`emes actuels non r´
esolu est de
d´eterminer si P = NP ou P 6= NP ;
I
La plupart des chercheurs croient que P 6= NP ;
I
Il s’agit d’un des sept probl`emes `
a un million de dollars :
http://www.claymath.org/millennium-problems
(`a ce jour, seule la conjecture de Poincar´
ea´
et´
e r´
esolue
en 2010).
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
16 / 43
La classe co-NP
I
Il existe d’autres classes de complexit´e importantes ;
I
On dit d’un probl`eme qu’il est de classe co-NP si son
compl´
ement est dans NP ;
I
Par exemple, le compl´
ement de PRIMED est
COMPOSITED, c’est-`
a-dire le probl`eme qui consiste `a
d´ecider si un nombre naturel est compos´
e ou non ;
I
Clairement, COMPOSITED est de classe NP (dire
pourquoi) ;
I
Par cons´equent, PRIMED est de classe co-NP ;
I
En fait, il a ´et´e d´emontr´e en 2002 que PRIMED est dans
P, et donc COMPOSITED aussi.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
17 / 43
Les diff´erents cas
co-NP
NP = co-NP
NP
P = NP ∩ co-NP
P = NP = co-NP
co-NP
P
A. Blondin Mass´
e (UQAC)
NP ∩ co-NP
NP
P
10 f´
evrier 2014
18 / 43
NP-compl´etude
I
Un des arguments principaux qui sugg`
ere que P 6= NP
est l’existence de probl`emes dits NP-complets ;
I
Il s’agit d’une classe de probl`emes qui sont bien NP, mais
on ne peut d´eterminer s’il existe un algorithme
polynomial pour le r´esoudre ;
I
Une autre particularit´e de la classe des probl`emes
NP-complets, c’est que si on r´eussit `
a r´esoudre un seul
probl`eme en temps polynomial, alors on peut r´esoudre
tous les autres en temps polynomial.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
20 / 43
Difficult´e d’un probl`eme NP
I
Soient P et Q deux probl`emes de d´
ecision ;
I
On ´ecrit P Q s’il existe un algorithme pour r´esoudre P
qui serait ex´ecutable en temps polynomial en supposant
qu’on peut r´esoudre Q en temps constant ;
I
La relation est r´
eflexive et transitive, mais pas
antisym´
etrique ;
I
On ´ecrit P ≡ Q si P Q et Q P ;
I
Clairement, si P Q ou si P ≡ Q et que B est de classe
P, alors A est de classe P.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
21 / 43
Probl`emes de d´ecision/optimisation
I
Jusqu’`a maintenant, nous nous sommes restreintes aux
probl`emes de d´
ecision ;
I
Soit HAMD le probl`eme de d´
ecider si un graphe G est
hamiltonien ou non ;
I
Soit HAM le probl`eme de trouver un cycle hamiltonien
dans un graphe G ;
I
Montrons que HAMD ≡ HAM ;
I
Consid´erons les fonctions suivantes :
I
EstHamiltonien(G : graphe) : bool´een ;
I
CycleHamiltonien(G : graphe) : cycle ou null.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
22 / 43
Probl`emes de d´ecision/optimisation (suite)
I
Impl´ementons EstHamiltonien(G) `
a partir de
CycleHamiltonien(G) ;
fonction EstHamiltonien(G : graphe) : bool´een
retourner CycleHamiltonien(G) 6= null
fin fonction
I
Il est ´evidemment plus compliqu´e d’impl´ementer
CycleHamiltonien(G) `
a partir de
EstHamiltonien(G) ;
I
Supposons que EstHamiltonien(G) s’ex´ecute en temps
Θ(h(n)) ;
I
Peut-on impl´ementer la fonction CycleHamiltonien(G)
en temps Θ(p(n)h(n)), o`
u p(n) est un polynˆ
ome ?
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
23 / 43
Probl`emes de d´ecision/optimisation (suite)
On utilise l’algorithme suivant :
1. Si ¬EstHamiltonien(G), alors retourner null ;
2. Sinon, soit u un sommet de G ;
3. Soit E l’ensemble des arˆ
etes incidentes a` u ;
4. Soit e = {u, v} ∈ E une arˆete telle que
EstHamiltonien(H − (E − {e})) ;
5. On supprime les arˆetes E − {e} de G ;
6. On recommence `
a l’´etape 3 en prenant u ← v et en retirant
de E le sommet u ;
7. Lorsqu’on a parcouru tous les sommets du graphe, on
retourne le cycle ainsi construit.
Complexit´
e?
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
24 / 43
D´efinition formelle
D´efinition
Un probl`eme de d´ecision P est dit NP-complet si
1. P est de classe NP ;
2. Pour tout probl`eme Q de classe NP, on a Q P .
I
En d’autres termes, un probl`eme est NP-complet s’il est
de classe NP et s’il est au moins aussi difficile que
n’importe quel autre probl`eme de classe NP ;
I
La prochaine ´etape consiste `
a montrer que l’ensemble des
probl`
emes NP-complets est non vide.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
25 / 43
Le probl`eme SAT
I
Consid´erons une expression bool´
eenne :
(p ∨ q) → (p ∧ q).
I
Existe-t-il une affectation de valeurs de v´
erit´
e `a p et `a
q pour que l’expression soit vraie ?
I
Qu’en est-il de
(p2 ∨ p3 ∨ ¬p4 ) ∧ (¬p1 ∨ p2 ∨ ¬p3 ) ∧ (¬p1 ∨ ¬p4 ∨ ¬p3 ) ?
I
Ce probl`eme d´enot´e SAT est appel´e probl`eme de
satisfaisabilit´
e.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
26 / 43
Forme normale
I
Il est plus pratique de manipuler les expressions logiques
sous forme k-CNF (conjunctive normal form) :
ki
` _
^
pij ,
i=1 j=1
o`
u pij ∈ {p1 , p2 , . . . , pn } et 1 ≤ ki ≤ k ;
I
Des cas particuliers du probl`eme SAT sont les suivants :
I
I
SAT-CNF est le probl`eme de d´ecider si une
expressions bool´eenne sous forme CNF est
satisfaisable ;
´
Etant
donn´e un entier positif k, SAT-k-CNF est le
probl`eme de d´ecider si une expression bool´eenne sous
forme k-CNF est satisfaisable.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
27 / 43
Th´eor`eme de Cook-Levin
Th´eor`eme
Le probl`eme SAT-CNF est NP-complet.
I
La d´emonstration est bas´ee sur les machines de Turing ;
Corollaire
Les probl`emes
I
SAT et
I
SAT-k-CNF, pour k ≥ 3,
sont NP-complets.
I
La d´emonstration se fait par r´
eduction.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
28 / 43
Cliques
I
Soit G = (V, E) un graphe non orient´
e;
I
On dit d’un ensemble U ⊆ V qu’il forme une clique dans
G si tous les sommets de U sont adjacents ;
I
´
Etant
donn´e un entier positif k, le probl`eme de d´
ecider s’il
existe une clique de taille k est d´enot´e par k-CLIQUED ;
I
Nous allons montrer que 3-CNF-SAT se r´
eduit au
probl`eme k-CLIQUED, c’est-`
a-dire que
3-CNF-SAT k-CLIQUED.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
30 / 43
R´eduction de 3-CNF-SAT a` k-CLIQUED
Soit l’expression bool´
eenne de k = 3 clauses
φ = (p1 ∨ ¬p2 ∨ ¬p3 ) ∧ (¬p1 ∨ p2 ∨ p3 ) ∧ (p1 ∨ p2 ∨ p3 ).
On construit un graphe comme suit :
p1
¬p2
¬p3
¬p1
p1
p2
p2
p3
p3
Clairement, la construction se fait en temps polynomial.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
31 / 43
R´eduction de 3-CNF-SAT a` k-CLIQUED
I
Il reste `a v´erifier que les deux conditions suivantes sont
´
equivalentes :
I
φ est satisfaisable ;
I
Le graphe admet une k-clique.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
32 / 43
R´eduction de 3-CNF-SAT a` k-CLIQUED (suite)
φ = (p1 ∨ ¬p2 ∨ ¬p3 ) ∧ (¬p1 ∨ p2 ∨ p3 ) ∧ (p1 ∨ p2 ∨ p3 ).
p1
¬p2
¬p3
¬p1
p1
p2
p2
p3
p3
I
Si φ est satisfaisable, alors il existe une affectation pour
laquelle au moins un litt´
eral est vrai dans chaque clause ;
I
Ils sont tous reli´
es puisque les seules arˆetes absentes sont
celles qui donnent une contradiction.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
33 / 43
R´eduction de 3-CNF-SAT a` k-CLIQUED (suite)
φ = (p1 ∨ ¬p2 ∨ ¬p3 ) ∧ (¬p1 ∨ p2 ∨ p3 ) ∧ (p1 ∨ p2 ∨ p3 ).
p1
¬p2
¬p3
¬p1
p1
p2
p2
p3
p3
I
Inversement, s’il existe une clique de taille k, alors elle
utilise exactement un sommet dans chaque clause ;
I
φ est satisfaisable en prenant n’importe quelle affectation
telle que chaque litt´
eral de la clique est vrai.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
34 / 43
Le probl`eme de la clique est NP-complet
En r´esum´e, on a le fait suivant :
Th´eor`eme
Le probl`eme k-CLIQUED est NP-complet.
Deux choses `a d´
emontrer :
I
k-CLIQUED est de classe NP ;
I
Il suffit de prendre comme certificat les sommets formant
la clique ;
I
SAT-3-CNF k-CLIQUED (on vient de le faire).
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
35 / 43
Autre r´eduction : `-CLIQUED k-VCD
Th´eor`eme
´
Etant
donn´e un entier positif k, le probl`eme k-VCD est
NP-complet.
D´
emonstration :
I
On montre que k-VCD est de classe NP ;
I
` partir d’une instance (G, k), on construit l’instance
A
(G, |V | − k) ;
I
On montre ensuite que si G a une clique U ⊆ V , o`
u
|U | = k, alors V − U est une couverture des arˆ
etes de G ;
I
Finalement, on montre que si G a une couverture U de
taille |V | − k, alors V − U est une clique de taille k.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
36 / 43
HAMD est NP-complet
Th´eor`eme
Le probl`eme HAMD est NP-complet.
I
Il est facile de voir que HAMD est de classe NP ;
I
La r´
eduction est par contre plus complexe.
I
En g´en´eral, on montre que
k-VCD HAMD
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
37 / 43
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAC)
Wx,y
s2
10 f´
evrier 2014
38 / 43
R´eduction (suite)
I
On sait d´ej`a que HAMD est de classe NP ;
I
On constate que la transformation est polynomiale ;
I
Pour chaque couverture des arˆ
etes, on peut construire
un cycle hamiltonien ;
I
` chaque cycle hamiltonien, on peut lui associer une
A
couverture des arˆ
etes par les sommets.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
39 / 43
Probl`emes NP-difficiles
I
Lorsqu’on ´etablit qu’un probl`eme est NP-difficile,
comment peut-on le traiter ?
I
Il y a essentiellement trois strat´egies ;
1. On con¸coit un algorithme exact, mais qui prend un
temps exponentiel, ce qui fonctionne pour des
instances de petite taille ;
2. On se restreint `
a des cas particuliers pour lesquels
on obtient des algorithmes polynomiaux ;
3. On utilise des approximations.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
41 / 43
Solutions approch´ees
Il existe plusieurs fa¸cons de calculer des solutions
approch´
ees :
I
Les algorithmes gloutons ;
I
Les m´
eta-heuristiques (algorithmes g´en´etiques,
´evolutionnaires, recherche locale, algorithmes tabous, recuit
simul´e) ;
I
La programmation lin´
eaire ;
I
Les algorithmes d’approximation.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
42 / 43
Algorithmes exacts
I
Au prochain cours, nous allons nous concentrer sur les
algorithmes exacts ;
I
Plus pr´ecis´ement, nous allons ´etudier une technique
appel´ee s´
eparation et ´
evaluation (en anglais,
branch-and-bound) ;
I
Dans la plupart des cas, on obtient un algorithme de
complexit´e exponentielle ;
I
L’objectif consiste alors `
a r´eduire le plus possible la
complexit´e pour qu’elle soit de la forme O(an ), o`
u a est le
plus proche possible de 1.
A. Blondin Mass´
e (UQAC)
10 f´
evrier 2014
43 / 43
© Copyright 2024 ExpyDoc
