La complexité d’un problème TP La classe NP
Complexité en temps et espace mémoire
Dr. Adel Benamira
Département d’Informatique
Université 08 Mai 45 Guelma, Algérie
Partie 02
1 / 29
La complexité d’un problème TP La classe NP
Plan
1 La complexité d’un problème
2 TP
3 La classe NP
2 / 29
La complexité d’un problème TP La classe NP
Les classes de Problèmes
Un problème est appelé problème de décision s’il consiste à
décider si un élément appartenant à une certaine famille a «
oui » ou « non » une certaine propriété.
3 / 29
La complexité d’un problème TP La classe NP
Les classes de Problèmes: La classe P.
4 / 29
La complexité d’un problème TP La classe NP
Les classes de Problèmes: La classe P.
⇒ La classe P (ou PTIME) est la classe des problèmes de
décision pour lesquels il existe un algorithme de résolution
polynomial en temps.
5 / 29
La complexité d’un problème TP La classe NP
Les classes de Problèmes: La classe P.
⇒ La classe P (ou PTIME) est la classe des problèmes de
décision pour lesquels il existe un algorithme de résolution
polynomial en temps.
⇒ Un problème de décision est dit praticable si il est dans P,
impraticable sinon.
6 / 29
La complexité d’un problème TP La classe NP
Les classes de Problèmes: La classe P.
"existe-t-il un algorithme praticable pour ce problème?" se
ramène à "ce problème est-il dans P?
7 / 29
La complexité d’un problème TP La classe NP
Les classes de Problèmes: La classe P.
"existe-t-il un algorithme praticable pour ce problème?" se
ramène à "ce problème est-il dans P?
Exemples de problèmes praticables ou non
"Etre pair" est P.
"Etre trié pour une liste d’entiers est P.
"Etre premier" est P ... On le sait depuis quelques années
seulement.
le problème des échecs généralisés -i.e. la taille de
l’échiquier est non fixée, on a une configuration, on
cherche à savoir si elle est gagnante- n’est pas P.
8 / 29
La complexité d’un problème TP La classe NP
Tester le coloriage d’un graphe
9 / 29
La complexité d’un problème TP La classe NP
Tester le coloriage d’un graphe
v0
Definition
Graphe G(V , E): v1 v2
V : ensemble des sommets.
E : ensemble des arêtes.
k : nombre de couleurs. v3
c : V → 1..k v4
v5
10 / 29
La complexité d’un problème TP La classe NP
Tester le coloriage d’un graphe
v0
Definition
Graphe G(V , E): v1 v2
V : ensemble des sommets.
E : ensemble des arêtes.
k : nombre de couleurs. v3 63
c : V → 1..k v4
v5
11 / 29
La complexité d’un problème TP La classe NP
Tester le coloriage d’un graphe
v0
Definition
Graphe G(V , E): v1 v2
V : ensemble des sommets.
E : ensemble des arêtes.
k : nombre de couleurs. v3 63
c : V → 1..k v4
v5
Ce problème est dans la classe P. En effet, il suffit de parcourir
les arêtes du graphe et de tester pour chacune si la couleur de
ses extrémités est la même.
12 / 29
La complexité d’un problème TP La classe NP
Trouver le coloriage d’un graphe c(v ) =?
13 / 29
La complexité d’un problème TP La classe NP
Trouver le coloriage d’un graphe c(v ) =?
v0
Definition
v1 v2
Graphe G(V , E):
V : ensemble des sommets.
E : ensemble des arêtes. v3
k : nombre de couleurs.
v4
v5
14 / 29
La complexité d’un problème TP La classe NP
Le temps polynomial non déterministe NP
15 / 29
La complexité d’un problème TP La classe NP
Le temps polynomial non déterministe NP
Definition (Vérification en temps polynomial)
Un problème B est vérifiable en temps polynomial si pour toute
instance x : si x ∈ B (certificat), il existe un algorithme (de taille
polynomiale en la taille de x) permettant de décider en temps
polynomial que x ∈ B. si x 6∈ B, il n’existe pas de tel algorithme.
16 / 29
La complexité d’un problème TP La classe NP
Le temps polynomial non déterministe NP
Definition (Vérification en temps polynomial)
Un problème B est vérifiable en temps polynomial si pour toute
instance x : si x ∈ B (certificat), il existe un algorithme (de taille
polynomiale en la taille de x) permettant de décider en temps
polynomial que x ∈ B. si x 6∈ B, il n’existe pas de tel algorithme.
Definition (Le temps polynomial non déterministe NP)
Un problème de décision B est dans NP s’il est vérifiable en
temps polynomial.
Formalisé par Cook (1971) et Levin (1973).
17 / 29
La complexité d’un problème TP La classe NP
Comment montrer qu’un problème est NP?
18 / 29
La complexité d’un problème TP La classe NP
Comment montrer qu’un problème est NP?
Pour montrer qu’un problème est NP, il faut:
définir la notion de certificat et montrer que la taille d’un
certificat est bornée polynomialement par la taille du
problème.
définir l’algorithme de Vérification et montrer qu’il est
polynomial (et correct...).
19 / 29
La complexité d’un problème TP La classe NP
Comment montrer qu’un problème est NP?
Pour montrer qu’un problème est NP, il faut:
définir la notion de certificat et montrer que la taille d’un
certificat est bornée polynomialement par la taille du
problème.
définir l’algorithme de Vérification et montrer qu’il est
polynomial (et correct...).
Exemple (ètre 3-coloriable: certificat)
Un certificat pour G(V , E) est juste un coloriage des noeuds.
On peut par exemple le représenter par un tableau de couleurs
indexé par les sommets. On a donc : taille du certificat ≤ taille
du graphe
20 / 29
La complexité d’un problème TP La classe NP
Comment montrer qu’un problème est NP?
Pour montrer qu’un problème est NP, il faut:
définir la notion de certificat et montrer que la taille d’un
certificat est bornée polynomialement par la taille du
problème.
définir l’algorithme de Vérification et montrer qu’il est
polynomial (et correct...).
Exemple (ètre 3-coloriable: vérificateur)
boolean A(col, G){
Pour chaque arc (s,d) de G
si col(s)=col(d) retourner Faux;
retourner Vrai;
}
21 / 29
La complexité d’un problème TP La classe NP
Définition Alternative
22 / 29
La complexité d’un problème TP La classe NP
Définition Alternative
Definition (via le non-déterminisme)
Un problème de décision B est dans NP si il existe un
algorithme non déterministe polynomial qui décide B.
23 / 29
La complexité d’un problème TP La classe NP
Définition Alternative
Definition (Algorithmes non déterministes polynômiaux)
24 / 29
La complexité d’un problème TP La classe NP
Définition Alternative
Definition (Algorithmes non déterministes polynômiaux)
Un algorithme non-déterministe peut être vu comme un
algorithme avec des instructions de type choix(i, 1..n): on
choisit aléatoirement un entier dans l’intervalle [1..n].
25 / 29
La complexité d’un problème TP La classe NP
Définition Alternative
Definition (Algorithmes non déterministes polynômiaux)
Un algorithme non-déterministe peut être vu comme un
algorithme avec des instructions de type choix(i, 1..n): on
choisit aléatoirement un entier dans l’intervalle [1..n].
Un algorithme non-déterministe A est dit polynômial s’il
existe un polynôme P tel que pour toute entrée u, tous les
calculs de A sur u ont une longueur d’exécution bornée par
Q(|u|).
26 / 29
La complexité d’un problème TP La classe NP
NP par rapport à P?
27 / 29
La complexité d’un problème TP La classe NP
NP par rapport à P?
P est inclus dans NP : tout problème P est un problème NP;
l’algorithme de vérification est l’algorithme de décision
28 / 29
La complexité d’un problème TP La classe NP
NP par rapport à P?
La conjecture NP 6= P?:
La conjecture a été émise par S. Cook en 1971 et le "Clay
Mathematics Institute" offre 01 million de dollars/127.78 million
de DZ à celui qui trouve la réponse à la question!
29 / 29
