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

pages

Français

Documents

Écrit par
Christophe Paul

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

Français

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

Voir

Publié par

pefav

Nombre de lectures

Langue

Français

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 diﬀ´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 diﬀ´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 diﬀ´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 diﬀ´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 satisﬁable
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 satisﬁable
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)

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

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

YouScribe

Le catalogue

Le service

Les conditions