View
55
Download
0
Category
Preview:
DESCRIPTION
Cours de graphes. Problèmes NP-complets. Réductions polynômiales. Les grandes lignes du cours. Définitions de base Connexité Les plus courts chemins Dijkstra et Bellmann-Ford Arbres Arbres de recouvrement minimaux Problèmes de flots Coloriage de graphes, graphes planaires Couplage - PowerPoint PPT Presentation
Citation preview
16 mars 2007
Cours de graphesProblèmes NP-complets.
Réductions polynômiales.
16 mars 2007
Les grandes lignes du cours• Définitions de base• Connexité• Les plus courts chemins• Dijkstra et Bellmann-Ford• Arbres• Arbres de recouvrement minimaux • Problèmes de flots• Coloriage de graphes, graphes
planaires• Couplage• Chemins d’Euler et de Hamilton• Problèmes NP-complets
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
R A P P E L S
S U R L A
N P – C O M P L E T U D E
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• La question :
• Y aurait-il par hasard des problèmes dont la complexité intrinsèque est exponentielle ?
• Pour un tel problème, tout algorithme pour le résoudre serait exponentiel en temps !
• La réponse :
• Probablement OUI !
• Malheureusement ! ! !
• On ne sait rien de définitif ! ! !
P = N Pou bien
P = N P
/
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• La classe de problèmes « P » !
• Ce sont les problèmes qui acceptent un algorithme :
– polynômial,
– déterministe,
– qui résout toutes les instances.
La complexité est un polynômeen termes de la taille du problème.
Il n’y a aucun élément de chance oud’indication venant de l’extérieur.
Aucune instancen’est trop difficile.
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• La classe de problèmes « N P » !
• Ce sont les problèmes qui acceptent un algorithme :
– polynômial,
– non-déterministe,
– qui résout toutes les instances.
Il peut y a avoir des élémentsde chance ou des
indications venant de l’extérieur.
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Nous remplaçons une exploration à l’aide du back-track
– par un appel à l’oracle.
• L’oracle répond au bout de . . . ?
– La complexité de l’oracle est bien-sûr en O ( 1 ) .
• Je sais réaliser un oracle en temps exponentiel !
– Il suffit de faire un back-track en cachette ! ! !
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Autre formulation de la classe de problèmes « N P » !
• Ce sont les problèmes qui :
– acceptent, pour chaque instance, un nombre borné de candidats à être la solution,
– pour lesquels, la vérification qu’un candidat quelconque est solution appartient à « P ».
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Théorème : P N PU
N P
P
P = N P c’est-à-dire N P \ P = o/? ?
? ? ? ? ?
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Définissons la classe « N P C », c’est-à-dire les problèmes « N-P-complets » :
N P
P
N P C
Ce seront les problèmes les plus difficiles de « N P » !
L’idée : Si eux sont dans « P », alors « P = N P » ! ! !
Facile.
Difficile.
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Il nous faut une notion de traduction !
– Soit un problème P : D -> BOOL
– Soit un problème P : D -> BOOL
• P se réduit polynômialement en P , noté P <= P
si et seulement si :
– il existe f : D -> D avec f e P– telle que pour tout x e D : P ( x ) = P ( f ( x ) )
11
22
1 12 2
1 2
1
1 2
P
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• L’idée derrière la traduction :
P1x Vrai ou Faux
Calcul !
P2f ( x )
Traduction !
Vrai ou FauxCalcul !
Le mêmerésultat !
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Définition :
• La classe « N P C » est la classe des problèmes P tels que :
– P e N P .
– Pour tout Q e N P on a : Q <= P .
• Tout le monde se réduit vers P .
• P est donc le plus difficile ! ! !
• Si P , P’ e N P C , alors il sont ex aequo en difficulté :
P <= P’ et P’ <= P .P P
P
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Et si « N P C » était vide ? ? ?– C’est-à-dire, un tel problème universel n’existe pas ! !
!
• Théorème (Cook, 1971) :
– SAT e N P C .
• Il n’y a pas plus difficile (dans N P C) que la logique.
• Principe de la preuve :– Tout problème dans « N P » peut être traduit en une
formule logique.– Analogie : Tout texte peut être traduit en une formule
alphabétique.
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
N P
P
N P CSAT
16 mars 2007
• Conséquences :
• S’il existe un seul problème P e N P C – pour lequel on trouve un algorithme en temps
polynômial et déterministe,
– alors P = N P !
• S’il existe un seul problème P e N P C – pour lequel on prouve qu’un algorithme en
temps polynômial et déterministe ne peut pas exister,
– alors P = N P !
Rappels sur la NP-complétude-----------------------------------------------------------------
/
16 mars 2007
Rappels sur la NP-complétude-----------------------------------------------------------------
• Concrètement :
• Vous avez un problème qui vous résiste ? • Essayez de savoir s’il est N-P-complet !
– le Garey and Johnson, ou Internet, ou . . .
• Comment prouver qu’il est N-P-complet ? ? ?
– Prouvez que votre problème P est dans N P et– prenez un problème A de N P C et montrez que A <= P
P
On vous donnela solution etvous vérifiezque c’en est
bien une !
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
Q U E L Q U E S
R E D U C T I O N S
P O L Y N O M I A L E S
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
SAT se réduit en CIRCUIT-SAT-----------------------------------------------------------------
• CIRCUIT-SAT– « n » variables logiques et un circuit logique
construit à partir des circuits de base et , ou ou not .
– La question : Le circuit peut-il rendre la valeur « Vrai » pour un choix adéquat des valeurs des variables ?
CIRCUIT-SAT est bien dans NP , car si on nousdonne une solution nous sommes capables de
vérifier que c’en est bien une en tempspolynômial et de façon déterministe !
16 mars 2007
SAT se réduit en CIRCUIT-SAT-----------------------------------------------------------------
• CIRCUIT-SAT– « n » variables logiques et un circuit logique
construit à partir des circuits de base et , ou ou not .
– La question : Le circuit peut-il rendre la valeur « Vrai » pour un choix adéquat des valeurs des variables ?
• La réduction :
– Nous allons traduire une formule logique de SAT en un circuit de CIRCUIT-SAT qui donne les mêmes résultats !
16 mars 2007
SAT se réduit en CIRCUIT-SAT-----------------------------------------------------------------
• La réduction :– Variable 3-SAT -> variable CIRCUIT-SAT.
– ù x -> x
– ( a v b v . . . v z ) -> a b . . . . . . z
– ( a b . . . z ) -> a b . . . . . . z
vv v
. . .La réductionest dans P !
. . .
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
• Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs négations ainsi que des conjonctions et des disjonctions binaires.
( ( x v ù y ) v ( ( y ( z v t ) ) ù x ) )
• Une formule 3-SAT FNC (forme normale conjonctive) est une formule qui comporte une conjonction n-aire composée de disjonctions avec trois littéraux ou leurs négations.
( a v ù b v c ) ( a v d v e ) . . . ( ù d v c v e )
v v
v v v
3-SAT FNC est bien dans NP , car si on nous donne unesolution nous sommes capables de vérifier que c’en est
bien une en temps polynômial et de façon déterministe !
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
• Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs négations ainsi que des conjonctions et des disjonctions binaires.
( ( x v ù y ) v ( ( y ( z v t ) ) ù x ) )
• Une formule 3-SAT FNC (forme normale conjonctive) est une formule qui comporte une conjonction n-aire composée de disjonctions avec trois littéraux ou leurs négations.
( a v ù b v c ) ( a v d v e ) . . . ( ù d v c v e )
• Nous allons « aplatir » notre formule SAT en une formule 3-SAT FNC.
v
v v
v v
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
• A une variable SAT nous associons une variable 3-SAT FNC.
• A une formule SAT de la forme ( A op B ) nous associons une nouvelle variable y pour laquelle nous affirmons que
– y est vraieet– y est équivalente à ( A op B )
• Ensuite, il suffit de traduire cette équivalence en une disjonction.
vy ( y <=> A op B )
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
• Une formule de la forme ( y <=> A op B ) correspond à une table de vérité avec 8 lignes. Nous en sélectionnons les 4 lignes qui sont fausses et nous les traduisons en une formule f qui est une disjonction de conjonctions :
( y A B ) v ( ù y ù A B ) v ( y ù A ù B ) v . . .
• La négation de f est la formule recherchée. D’après de « De Morgan », nous obtenons :
( ù y v ù A v ù B ) ( y v A v ù B ) ( ù y v A v B ) . . .
v
v v v v v v
v v
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
• Une formule de la forme ( y <=> A op B ) correspond à une table de vérité avec 8 lignes. Nous en sélectionnons les lignes qui sont fausses et nous les traduisons en une formule f qui est une disjonction de conjonctions :
( y A B ) v ( ù y ù A B ) v ( y ù A ù B )
• La négation de f est la formule recherchée. D’après de « De Morgan », nous obtenons :
( ù y v ù A v ù B ) ( y v A v ù B ) ( ù y v A v B )
• La même approche reste vraie pour tous les opérateurs binaires, comme et , ou , => , <=> , . . .
v
v v v v v v
v
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
U N
E X E M P L E
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
( ( ( x => x ) x ) v x )v
2 3 2 1
v
x 1
v
x 2=>
x 3x 2
y 1
y 2
y 3
y 1
v( y <=> ( y v x ) )1v
v
( y <=> ( y x ) )2
( y <=> ( x => x ) )3 2 3
2 1
3 2
v
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
( ( ( x => x ) x ) v x )v
2 3 2 1
y 1
v( y <=> ( y v x ) )1v
v
( y <=> ( y x ) )2
( y <=> ( x => x ) )3 2 3
2 1
3 2
v
y 3 x 2 x 3 . . .
0 0 0 00 0 1 00 1 0 1
0 1 1 01 0 0 1
1 0 1 11 1 0 01 1 1 1
f = ( ù y ù x ù x )
v ( ù y ù x x ) v . . .
v
3 2
v
3
v
3 2
v
3
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
( ( ( x => x ) x ) v x )v
2 3 2 1
y 1
v( y <=> ( y v x ) )1v
v
( y <=> ( y x ) )2
( y <=> ( x => x ) )3 2 3
2 1
3 2
v
y 3 x 2 x 3 . . .
0 0 0 00 0 1 00 1 0 1
0 1 1 01 0 0 1
1 0 1 11 1 0 01 1 1 1
ù f = ( y v x v x )
( y v x v ù x ) . . .
v
3 2 3
v
3 2 3
16 mars 2007
SAT se réduit en 3-SAT FNC-----------------------------------------------------------------
( ( ( x => x ) x ) v x )v
2 3 2 1
y 1
v( y <=> ( y v x ) )1v
v
( y <=> ( y x ) )2
2 1
3 2
v
y 3 x 2 x 3 . . .
0 0 0 00 0 1 00 1 0 1
0 1 1 01 0 0 1
1 0 1 11 1 0 01 1 1 1
( y v x v x )3 2 3
v( y v x v ù x )3 2 3
v. . .
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
• Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns des autres !
Une clique de3 sommets !
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
• Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns des autres !
• Question : Y a-t-il G une clique de k sommets ?
• CLIQUE est dans NP car nous savons vérifier dans P si un ensemble de sommets est une clique ou non !
L’unique cliquede 4 sommets !
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
F = C . . . Cv
1
C = T v T v T i i,1 T = x | ù xpi,j p
k
v
i,2 i,3
• Soit une formule 3-SAT FNC constituée de k conjonctions :
• Nous allons montrer que cette formule peut être rendue vraie si et seulement s’il existe une clique de taille k dans un certain graphe.
• CLIQUE sera donc au moins aussi difficile que 3-SAT FNC, c’est-à-dire vraisemblablement exponentiel en général.
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
• La construction du graphe :
• A chaque terme T nous associons un sommet.
• Les sommets T et T sont voisins dans le graphe ssi :
– i et m sont différents,– les termes ne sont pas la négation l’un de l’autre.
i,j
i,j m,n
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
• La construction du graphe :
• A chaque terme T nous associons un sommet.
• Les sommets T et T sont voisins dans le graphe ssi :
– i et m sont différents,– les termes ne sont pas la négation l’un de l’autre.
• Cette construction est clairement déterministe et peut se faire en temps polynômial.
i,j
i,j m,n
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3
v ( x v x v x )1 2 4
v
x1 ù x 2 ù x 3
ù x1
x 2
x 3
x1
x 2
x 4
En construction . . . NONCOMPATIBLES !
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3
v ( x v x v x )1 2 4
v
x1 ù x 2 ù x 3
ù x1
x 2
x 3
x1
x 2
x 4
Le voilà !
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3
v ( x v x v x )1 2 4
v
• Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !
• Autrement dit, ils doivent correspondre à une clique que nous pouvons former dans le graphe !
• Rendre vraie la formule ou trouver une clique dans le graphe sont donc des problèmes de même difficulté ! ! !
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3
v ( x v x v x )1 2 4
v
x1 ù x 2 ù x 3
ù x1
x 2
x 3
x1
x 2
x 4
Une solution !
16 mars 2007
3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------
( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3
v ( x v x v x )1 2 4
v
x1 ù x 2 ù x 3
ù x1
x 2
x 3
x1
x 2
x 4
Une autre solution !
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
CLIQUE se réduit en VERTEX COVER-----------------------------------------------------------------
• Nous nous donnons un graphe G = ( V , E ) avec n sommets et une constante naturelle k .
• Question : Pouvons-nous trouver un sous-ensemble V’ d’au plus k sommets de façon à ce que toute arête ait au moins une extrémité dans V’ ?
k = 2
OUI ! ! !
Les arêtes sont dansl’ensemble ou elles
traversent la frontière !
Nous sommescapablesde vérifierune solution entemps polynômialet déterministe ! ! !
16 mars 2007
CLIQUE se réduit en VERTEX COVER-----------------------------------------------------------------
• Pourquoi est-ce un VERTEX COVER ?• C’en est un parce que les sommets en dehors de
V’ n’ont aucune arête en commun ! ! !• Autrement dit, les arêtes absentes comportent
une clique de taille | V | – | V’ | , c’est-à-dire n – k .
Considérons legraphe G’ qui
contient les arêtesabsentes de G !
G’ possède alorsune clique detaille n – k .
16 mars 2007
CLIQUE se réduit en VERTEX COVER-----------------------------------------------------------------
• Pour un graphe avec n sommets, il est équivalent de – de trouver un VERTEX COVER de taille k ou– de trouver une CLIQUE de taille n – k dans le
graphe complémentaire.
Considérons legraphe G’ qui
contient les arêtesabsentes de G !
G’ possède alorsune clique detaille n – k .
La transformation estdéterministe etpolynômiale.
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous avons :
– un ensemble S d’entiers naturels non nuls,– une constante k .
• La question est la suivante :
– Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?
S = { 13 , 17 , 23 , 41 , 65 , 69 } et k = 105
OUI ! ! !Une autre solution ! ! !
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous avons :
– un ensemble S d’entiers naturels non nuls,– une constante k .
• La question est la suivante :
– Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?
• Le problème est dans NP , car la vérification est polynômiale et déterministe !
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous considérons une matrice d’adjacence :
4
3
5a
b
cd
e
f
a b c d e f
12345
11000 Il y a deux occurrences
de 1 sur chaque colonne !
12
L’arête b est incidenteaux sommets 1 et 2 !
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous considérons une matrice d’adjacence :
4
12 3
5a
b
cd
e
f
a b c d e f
12345
11000
10010
10001
00011
01100
00101
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous rajoutons une matrice identité !• Nous rajoutons une colonne au début !• A lire en base 4, il n’y a pas de retenue !• Et les nombres sont tous différents !• Chaque ligne de la matrice donne un nombre de S !
a b c d e f
12345
11000
10001
00011
01100
00101
0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0
10010000001
11111000000
3 3 3 3 33| V |
+= 1= 4= 16= . . .
= x= y
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--Le graphe contient un VERTEX COVER de taille ksi nous pouvons choisir de telles lignes afinque chaque colonne comporte2 occurrences de 1 !
4
12 3
5a
b
cd
e
f
a b c d e f
12345
11000
10010
10001
00011
01100
00101
V
{ 1 , 2 , 5 } est un VERTEXCOVER de 3 sommets ! ! !
16 mars 2007Soit k = k
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous rajoutons une matrice identité !• Nous rajoutons une colonne au début !• A lire en base 4, il n’y a pas de retenue !• Et les nombres sont tous différents !• Chaque ligne de la matrice donne un nombre de S !
a b c d e f
12345
11000
10001
00011
01100
00101
0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0
10010000001
11111000000
2 2 2 2 22
+= 1= 4= 16= . . .
= x= y
S V
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous avons un VERTEX COVER de taille k ssi nous avons un SUBSET SUM de valeur k .
• Soit le VERTEX COVER.
• Chaque colonne comporte au moins une fois le 1 ! ! ! Nous choisissons d’autres lignes pour compléter à 2 !
V
S
11000
10001
00011
01100
00101
0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0
10010000001
11111000000
Nous avons une somme de k = k V 2 2 2 2 22S
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--• Nous avons un VERTEX COVER de taille k ssi nous avons un SUBSET SUM de valeur k .
• Soit le SUBSET SUM.
• Nous en extrayons un VERTEX COVER !
V
S
11000
10001
00011
01100
00101
0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0
10010000001
11111000000
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--
U N
E X E M P L E
N U M E R I Q U E
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--11000
10001
00011
01100
00101
0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0
10010000001
11111000000
1 =4 =
16 =64 =
256 =1024 =
5440 =4356 =4101 =5136 =4177 =
Le VERTEX COVER{ 1 , 2 , 5 } donne :
544043564177
14
161024
15018
k = 15018 = 3 S 2 2 2 2 22
16 mars 2007
VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------
--11000
10001
00011
01100
00101
0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0
10010000001
11111000000
1 =4 =
16 =64 =
256 =1024 =
5440 =4356 =4101 =5136 =4177 =
Le VERTEX COVER{ 2 , 4 , 5 } donne :
435651364177
14
64256
102415018
k = 15018 = 3 S 2 2 2 2 22
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
SUBSET SUM se réduit en 0-1 LINEAR PROG.-------------------------------------------------------------------------
-------• Nous avons un n-uplet X de variables qui
prennent 0 ou 1 comme valeurs.
• Nous avons p inéquations d’inconnue X :
• La question : Pouvons-nous trouver un vecteur X qui satisfait toutes les inéquations ?
• Le problème est bien dans NP !
a x + . . . + a x <= b1,1 1 1,n n 1
a x + . . . + a x <= bp,1 1 p,n n p
. . .Sous formematricielle :
A X <= B
16 mars 2007
SUBSET SUM se réduit en 0-1 LINEAR PROG.-------------------------------------------------------------------------
-------• Soit l’ensemble S = { s , . . . , s } de
nombres et la constante k .
• Nous construisons les deux inégalités :
• La transformation est dans P .• Trivial : k peut être obtenue comme somme de
nombres de S , si et seulement si, le système de programmation 0–1 admet une solution.
s x + . . . + s x <= k1 1 n n Celles-ciéquivalent àune égalité !
1 n
– s x – . . . – s x <= – k1 1 n n
==
16 mars 2007
Réductions polynômiales-----------------------------------------------------------------
• Nous construirons les réductions polynômiales suivantes :
£ PSAT
£P
CIRCUIT-SAT
£P3-SAT FNC
SUBSET SUM
CLIQUE VERTEX COVER£P
et VERTEX C.£P£ P
£P SET PARTITION
0-1 LINEAR PROG.
16 mars 2007
SUBSET SUM se réduit en SET PARTITION-------------------------------------------------------------------------
----
S = { 17 , 37 , 48 , 70 , 76 }
OUI ! ! !
• Le problème SET PARTITION consiste à savoir si un ensemble S de nombres naturels peut être décomposé en deux sous-ensembles de nombres de sommes égales.
• Le problème est bien dans NP !
16 mars 2007
SUBSET SUM se réduit en SET PARTITION-------------------------------------------------------------------------
----• Soit l’ensemble d’entiers S et la constante k
pour lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.
• Les deux problèmes sont équivalents. La transformation
est polynômiale et déterministe.
• Preuve ( => ) :– Si A est un sous-ensemble de S de somme k ,
alors son complément AC est de somme T–k .– Il suffit de choisir les ensembles B = A v { T–
k+1 } et BC = AC v { k+1 } pour avoir une solution à SET PARTITION avec la somme identique T+1 .
16 mars 2007
SUBSET SUM se réduit en SET PARTITION-------------------------------------------------------------------------
----• Soit l’ensemble d’entiers S et la constante k
pour lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.
• Les deux problèmes sont équivalents. La transformation
est polynômiale et déterministe.
• Preuve ( <= ) :– Soient B et BC une partition de Z en solution
de SET PARTITION. k+1 et T–k+1 ne figurent pas dans le même sous-ensemble.
– Si T–k+1 est dans B , il suffit de choisir A égal à B \ { T–k+1 } pour que A soit un sous-ensemble de S de somme k et donc une solution à SUBSET SUM.
16 mars 2007
Un problème curieux-----------------------------------------------------------------
I S O M O R P H I S M E S
D E
G R A P H E S
16 mars 2007
Un problème curieux-----------------------------------------------------------------• Deux graphes sont-ils identiques à
(re-)nommage des sommets près ? A1
B2
C3D4
E5G6
H7
I8J9
K10
A1 B2
C3E5
D4
G6H7
I8K10
J9
16 mars 2007
Un problème curieux-----------------------------------------------------------------
• GRAPH ISOMORPHISM est bien-sûr dans NP !
• On sait résoudre le problème dans P pour de nombreuses classes de graphes !
• On ne connaît aucun algorithme dans P qui résolve toutes les instances !
• On ne sait pas si GRAPH ISOMORPISM est dans P ?
• On ne sait toujours pas si GRAPH ISOMORPHISM est N–P–complet ! ! !
16 mars 2007
Synthèse-----------------------------------------------------------------
• Problèmes NP-complets.
• Réductions polynômiales.
Recommended