Les algorithmes La theorie de la complexite: un peu d'histoire La classe P La classe NP La classe PEspace Reductions parcimonieuses

Christophe Paul

Description

Les algorithmes La theorie de la complexite: un peu d'histoire La classe P La classe NP La classe PEspace Reductions parcimonieuses Complexite avancee - UMIN 345 Theorie de la NP-Completude (2) Christophe PAUL September 24, 2007 Christophe PAUL Complexite avancee - UMIN 345 Theorie de la NP-Completude (2)

• complexite avancee - umin


• classe co ?


• x1 x2x2


• reductions parcimonieusesquelques


• classe np


• theorie de la complexite

Sujets

• Théorie de la complexité
• exercice
• exercices

Informations

• Publié par: pefav
• Nombre de lectures: 58
• Langue: Français

Extrait

Les algorithmes La th´eorie de la complexit´e: un peu d’histoire La classe P La classe NP La classe PEspace R´eductions parcimonieuses
Complexit´e avanc´ee - UMIN 345
Th´eorie de la NP-Compl´etude (2)
Christophe PAUL
September 24, 2007
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2)Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaQuclaelquessse Pr´eductionsLa classe NPLa classeLa clcoasse−PEsNPpacBonnee R´eductis caractons ´eripasati rcimonsonieuses
1 Les algorithmes
2 La th´eorie de la complexit´e: un peu d’histoire
3 La classe P
4 La classe NP
Quelques r´eductions
La classe co−NP
Bonnes caract´erisations
5 La classe PEspace
6 R´eductions parcimonieuses
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2){B,T,F} est un triangle de G ainsi que∀i,{B,x ,x}i i
Observation: ∀i, x et x sont colori´es diff´erement par T et F.i i`a chaque clause, on associe le gadget suivant
1 3-coloration appartient clairement `a NP
2 Construction d’un graphe `a partir d’une instanceI de 3-sat:
V contient 3 sommets B, T et F ainsi que 2 sommets x et xi i
pour chaque variable x .i
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaQuclaelquessse Pr´eductionsLa classe NPLa classeLa clcoasse−PEsNPpacBonnee R´eductis caractons ´eripasati rcimonsonieuses
Exercice : Montrer que 3-sat6 3-colorationK
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2){B,T,F} est un triangle de G ainsi que∀i,{B,x ,x}i i
`a chaque clause, on associe le gadget suivant
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaQuclaelquessse Pr´eductionsLa classe NPLa classeLa clcoasse−PEsNPpacBonnee R´eductis caractons ´eripasati rcimonsonieuses
Exercice : Montrer que 3-sat6 3-colorationK
1 3-coloration appartient clairement `a NP
2 Construction d’un graphe `a partir d’une instanceI de 3-sat:
V contient 3 sommets B, T et F ainsi que 2 sommets x et xi i
pour chaque variable x .i
Observation: ∀i, x et x sont colori´es diff´erement par T et F.i i
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2)Observation: ∀i, x et x sont colori´es diff´erement par T et F.i i
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaQuclaelquessse Pr´eductionsLa classe NPLa classeLa clcoasse−PEsNPpacBonnee R´eductis caractons ´eripasati rcimonsonieuses
Exercice : Montrer que 3-sat6 3-colorationK
1 3-coloration appartient clairement `a NP
2 Construction d’un graphe `a partir d’une instanceI de 3-sat:
V contient 3 sommets B, T et F ainsi que 2 sommets x et xi i
pour chaque variable x .i
{B,T,F} est un triangle de G ainsi que∀i,{B,x ,x}i i
T F
Bx x
1 3
xx 3
1
x x
2 2
`a chaque clause, on associe le gadget suivant
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2)Observation: ∀i, x et x sont colori´es diff´erement par T et F.i i`a chaque clause, on associe le gadget suivant
x
3(x ∨x ∨x )1 2 3
x x
1 T 2 F
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaQuclaelquessse Pr´eductionsLa classe NPLa classeLa clcoasse−PEsNPpacBonnee R´eductis caractons ´eripasati rcimonsonieuses
Exercice : Montrer que 3-sat6 3-colorationK
1 3-coloration appartient clairement `a NP
2 Construction d’un graphe `a partir d’une instanceI de 3-sat:
V contient 3 sommets B, T et F ainsi que 2 sommets x et xi i
pour chaque variable x .i
{B,T,F} est un triangle de G ainsi que∀i,{B,x ,x}i i
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2)Si au moins un terme de la clause recoit¸ la couleur T, alors le
graphe est 3-coloriable.
4 La construction du graphe est clairement polynomiale.
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaQuclaelquessse Pr´eductionsLa classe NPLa classeLa clcoasse−PEsNPpacBonnee R´eductis caractons ´eripasati rcimonsonieuses
Exercice : Montrer que 3-sat6 3-colorationK
1 3-coloration appartient clairement `a NP
2 Construction d’un graphe `a partir d’une instanceI de 3-sat
T F
Bx x
1 3 x
3
xx 3
1 x x
1 T 2 Fx x
2 2
3 G est 3-coloriable ssiI est satisfiable
Si aucun terme de la clause re¸coit la couleur T, alors le graphe
n’est pas 3-coloriable.
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2)Si au moins un terme de la clause recoit¸ la couleur T, alors le
graphe est 3-coloriable.
4 La construction du graphe est clairement polynomiale.
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaQuclaelquessse Pr´eductionsLa classe NPLa classeLa clcoasse−PEsNPpacBonnee R´eductis caractons ´eripasati rcimonsonieuses
Exercice : Montrer que 3-sat6 3-colorationK
1 3-coloration appartient clairement `a NP
2 Construction d’un graphe `a partir d’une instanceI de 3-sat
T F ????
Bx x
1 3
x
3
xx 3
1
x xx x 1 T 2 F2 2
3 G est 3-coloriable ssiI est satisfiable
Si aucun terme de la clause re¸coit la couleur T, alors le graphe
n’est pas 3-coloriable.
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (2)