Chapitre 12 : Quelques problèmes NP-complets

R ponse: D cider sil existe une partition V = V1*V2 telle que le nombre dar tes

entre V1 et V2 soit au moins k.

Th or me 12.6 Le probl me COUPURE MAXIMALE est NP-complet.

D monstration : On r duit NAE3SAT COUPURE MAXIMALE. Supposons

donc donn e une instance de NAE3SAT, dans laquelle on peut supposer sans perte

de g n ralit quune clause ne contient pas simultan ment une variable et son com-

pl mentaire. Quitte remplacer u ( v par ((u ( v ( w) ' (u ( v ( w)), on peut

aussi supposer que chaque clause contient exactement 3 litt raux. Enn, si lon a deux

clauses (u ( v ( w) et (u ( v ( z), on peut, en introduisant deux variables t1 et t2

et en proc dant comme pour r duire NAE4SAT NAE3SAT, r crire ces deux clauses

comme (u ( t1 ( t2) ' (v ( w ( t1) ' (v ( z ( t2). Bref, on peut donc supposer que

deux clauses donn es ont au plus une variable en commun.

On note x1, , xn les variables de la formule F .

On va construire un graphe G = (V, E) de la fa on suivante : G poss de 2n som-

mets o pour chaque variable u de F , correspondent deux sommets u et u. G poss de

une ar te entre chaque couple de sommets (u, v) tels que u et v apparaissent dans la

m me clause, et une ar te entre les sommets u et u pour toute variable u.

Les r ductions dans le premier paragraphe de la preuve permettent de voir qu

chaque clause correspond un triangle et que deux de ces triangles ont des ar tes dis-

tinctes.

Si on note n le nombre de variables, et m le nombre de clauses, le graphe G a donc

2n sommets et 3m + n ar tes. Il est alors facile de voir que le nombre dar tes dans une

12.1. QUELQUES PROBL MES NP-COMPLETS

5

coupure correspondant une affectation NAE3SAT valide est 2m + n : lar te entre u

et u pour chaque variable u, et deux des ar tes du triangle uvw pour chaque clause

u ( v ( w.

Inversement, toute coupure de G a au plus (2m + n) ar tes, car une coupure ne peut

inclure que deux ar tes par triangle associ une clause. Par cons quent, une coupure

de valeur 2m + n fournit imm diatement une affectation NAE3SAT valide.

En dautres termes, r soudre linstance de NAE3SAT revient r soudre COU-

PURE MAXIMALE sur (G, 2m + n).

La r duction tant polynomiale, et puisque COUPUREMAXIMALE est dans NP

(cid:3)

car la donn e de V1 est un certicat valide v riable en temps polynomial.

12.1.3 Autour de CIRCUIT HAMILTONIEN

Le probl me CIRCUIT HAMILTONIEN est souvent la base de propri t s li es

aux chemins dans les graphes (nous reprenons la d nition de ce probl me, m me sil

a d j t d ni dans le chapitre pr c dent).

D nition 12.7 (CIRCUIT HAMILTONIEN)

Donn e: Un graphe G = (V, E) (non-orient ).

R ponse: D cider sil existe un circuit hamiltonien, cest- -dire un chemin de G

passant une fois et une seule par chacun des sommets et revenant son point de

d part.

Th or me 12.7 Le probl me CIRCUIT HAMILTONIEN est NP-complet.

D monstration : On va d montrer ce fait en r duisant RECOUVREMENT DE

SOMMETS ce probl me.

La technique consiste construire, partant dune instance de RECOUVREMENT

DE SOMMETS, un graphe dans lequel chaque ar te initiale sera remplac e par un

motif admettant exactement deux chemins hamiltoniens, cest- -dire des chemins

visitant une fois et une seule chaque sommet. Lun de ces deux chemins correspondra

au cas o le sommet correspondant appartient la couverture, lautre au cas o il ny

appartient pas.

Il reste ensuite pr ciser comment recoller ces diff rents motifs pour quun circuit

hamiltonien global corresponde exactement une r union de chemins hamiltoniens

travers chaque motif, et pour assurer quon obtient bien le bon r sultat au probl me

RECOUVREMENT DE SOMMETS initial en r solvant CIRCUIT HAMILTONIEN

dans ce graphe.

Notons (G = (V, E), k) linstance de RECOUVREMENT DE SOMMETS tu-

di e.

Le motif que nous allons utiliser est le suivant :

6

CHAPITRE 12. QUELQUES PROBL MES NP-COMPLETS

u1

u2

u3

u4

u5

u6

v1

v2

v3

v4

v5

v6

Pour obtenir un parcours de ce motif traversant une fois et une seule chaque som-

met, seules deux solutions sont possibles : soit un passage en deux fois, une fois

u1u2u3u4u5u6 puis ult rieurement v1v2v3v4v5v6 (dans un sens ou dans lautre) ; ou

alors un passage en une seule fois u1u2u3v1v2v3v4v5v6u4u5u6 (ou le m me en inver-

sant les u et les v).

chaque ar te (u, v) du graphe de d part, on associe un motif de ce type, en faisant

correspondre le sommet u au c t u et le sommet v au c t v. On raccorde ensuite entre

eux bout bout tous les c t s de tous les motifs correspondant un m me sommet ; on

forme donc une cha ne associ e un sommet donn , avec encore deux sorties libres.

On raccorde alors chacune de ces deux sorties k nouveaux sommets s1, , sk. On

note le graphe ainsi construit H dans la suite.

Supposons maintenant donn un recouvrement du graphe initial de taille k, dont les

sommets sont {g1, , gk}. On peut alors construire un circuit hamiltonien de H de la

fa on suivante :

partir de s1 ;

parcourir la cha ne g1 de la fa on suivante. Quand on traverse une ar te (g1, h),

si h est aussi dans la couverture, on traverse simplement le c t g1, sinon, on

parcourt les deux c t s simultan ment ;

une fois la cha ne g1 nie, on revient en s2 et on repart par g2 et ainsi de suite.

Il est clair que tous les sommets sk sont atteints une fois et une seule.

Consid rons un sommet h du motif correspondant une ar te (u, v). On peut tou-

jours supposer que u est dans la couverture, disons u = g1. Il sensuit que si h est du

c t de u, h sera atteint une fois au moins. On voit en vertu du second item quil ne sera

plus atteint dans la suite. Si h est du c t de v, et que v nest pas dans la couverture,

h est parcouru lors du parcours de u. Si v = gi, h est parcouru lors du parcours de

la cha ne correspondant gi et ce moment-l seulement. On a donc bien un circuit

hamiltonien.

R ciproquement, supposons que lon dispose dun circuit hamiltonien de H. La

construction de notre motif impose que venant dun sommet si, on traverse enti rement

une cha ne u puis lon passe un autre des sommets sj. On traverse ainsi k cha nes ;

les k sommets correspondants forment alors une couverture. En effet, si (u, v) est une

ar te, le motif correspondant est parcouru par le chemin hamiltonien ; or il ne peut

l tre que lors du parcours dune boucle correspondant une des deux extr mit s de

lar te.

donc bien NP-complet.

Enn, la r duction est trivialement polynomiale. CIRCUIT HAMILTONIEN est

(cid:3)

Comme dans la section pr c dente, on peut alors en d duire la NP-compl tude de

nombreuses variantes.

12.1. QUELQUES PROBL MES NP-COMPLETS

7

D nition 12.8 (VOYAGEUR DE COMMERCE)

Donn e: Un couple (n, M ), o M est une matrice n n dentiers et un entier k.

R ponse: D cider sil existe une permutation de [1, 2, , n] telle que

(cid:88)

1didn

M (i) (i+1) d k.

Corollaire 12.2 Le probl me VOYAGEUR DE COMMERCE est NP-complet.

Ce probl me porte ce nom, car on peut voir cela comme l tablissement de la tour-

n e dun voyageur de commerce devant visiter n villes, dont les distances sont donn es

par la matrice M de fa on faire moins de k kilom tres.

D monstration :

On r duit CIRCUIT HAMILTONIEN VOYAGEUR DE COMMERCE. Pour ce

faire, tant donn un graphe G = (V, E), on pose V = {x1, , xn}. On consid re

alors la matrice M n n dentiers telle que

Mi,j =

(cid:26) 1

2

si (i, j) E;

sinon.

Montrons alors que CIRCUIT HAMILTONIEN(V, E) ssi VOYAGEUR DE COMMERCE(n, M, n).

Sil existe un circuit hamiltonien dans G on peut en effet construire la permutation

comme d crivant lordre de parcours des sommets du graphe G : par construction, la

somme des distances des ar tes sur ce circuit vaudra n.

Inversement, tant donn e une permutation avec cette propri t , le fait que les n1

termes de la somme soient au moins gaux 1 implique quils sont tous gaux 1, et

donc que les ar tes ( (i), (i+1)) existent dans le graphe G : on a donc bien un circuit

(cid:3)

hamiltonien.

D nition 12.9 (CIRCUIT LE PLUS LONG)

Donn e: Un graphe G = (V, E) non-orient , avec des distances sur chaque ar te,

un entier r.

R ponse: D cider sil existe un circuit de G ne passant pas deux fois par le m me

sommet dont la longueur est e r.

Corollaire 12.3 Le probl me CIRCUIT LE PLUS LONG est NP-complet.

D monstration : On construit une r duction partir de CIRCUIT HAMILTO-

NIEN : pour cela, un graphe G pour CIRCUIT HAMILTONIEN, on associe chaque

ar te le poids 1. La recherche dun cycle hamiltonien est alors trivialement identique

(cid:3)

la recherche dun circuit de longueur e n dans le graphe.

12.1.4 Autour de 3-COLORABILITE

Nous avons d j d nit ce que nous appelions un (bon) coloriage de graphes dans

le chapitre pr c dent. Le plus petit entier k tel quun graphe soit (bien) coloriable est

appel le nombre chromatique du graphe.

Il est connu que les graphes planaires sont toujours coloriables avec 4 couleurs.

8

CHAPITRE 12. QUELQUES PROBL MES NP-COMPLETS

D nition 12.10 (3-COLORABILITE)

Donn e: Un graphe G = (V, E) non-orient .

R ponse: D cider sil existe un coloriage du graphe utilisant au plus 3 couleurs.

Th or me 12.8 Le probl me 3-COLORABILITE est NP-complet.

D monstration : 3-COLORABILITE est dans NP, car la donn e des sommets co-

lor s par chacune des 3 couleurs constitue un certicat v riable en temps polynomial.

On va r duire 3-SAT 3-COLORABILITE. On se donne donc une conjonction de

clauses 3 litt raux, et il nous faut partir de l construire un graphe. Comme dans les

autres r ductions de 3-SAT, il faut parvenir traduire deux contraintes : une variable

peut prendre la valeur 0 ou 1 dune part, et les r gles d valuation dune clause dautre

part.

On construit un graphe ayant 3 + 2n + 5m sommets, les trois permiers sont not s

V RAI, F AU X, N SP . Ces trois sommets sont reli s deux deux en triangle, de

sorte quils doivent tre tous trois de couleurs diff rentes. On appellera les couleurs

correspondantes V RAI, F AU X, N SP .

On associe un sommet chaque variable et au compl mentaire de chaque variable.

Pour assurer quune variable prenne la valeur V RAI ou F AU X, pour chaque variable

xi on construit un triangle dont les sommets sont xi, xi, et N SP . Cela impose que

soit couleur(xi) = V RAI et couleur( xi) = F AU X, ou couleur(xi) = F AU X

et couleur( xi) = V RAI.

Il nous reste donc encoder les r gles d valuation dune clause. Pour ce faire, on

introduit le sous-graphe suivant, qui correspond une clause x ( y ( z :

3

4

2

x

y

z

0

1

V RAI

Il est facile de voir que si ce motif (o les trois sommets distingu s et les triangles

construits sur les variables sont implicites) est 3-coloriable, alors les sommets 0 et

1 sont F AU X et N SP . Si 1 est F AU X, comme un sommet correspondant une

variable doit tre V RAI ou F AU X, on a couleur(z) = V RAI. Si 0 est F AU X,

alors 2 ne peut pas tre F AU X, donc 3 ou 4 lest, et la variable correspondante est

colori e V RAI.

R ciproquement, si lune des variables est vraie, on peut facilement construire une

3-coloration du motif.

Consid rons alors le graphe form des trois sommets distingu s, des triangles for-

m s sur les variables, et des motifs donn s. Si ce graphe est 3-coloriable, alors en

particulier tout sous-graphe est coloriable. Les triangles de variables sont en particu-

lier coloriables. partir dune 3-coloration du graphe, on construit une affectation de

valeurs de v rit en mettant 1 toutes les variables colori es par V RAI. Cette affec-

tation est coh rente (une variable et son compl mentaire ont bien une valeur oppos e)

12.1. QUELQUES PROBL MES NP-COMPLETS

9

et au moins une variable par clause est 1, en vertu des propri t s du motif ci-dessus.

Inversement, tant donn une affectation de valeurs de v rit , il est ais de d duire une

3-coloration du graphe.

Lexistence dune 3-coloration du graphe est donc quivalente la satisfaisabilit

de la formule initiale.

La r duction est manifestement polynomiale ; on a donc bien prouv que 3-SAT se

(cid:3)

r duisait 3-COLORABILITE ; ce dernier est donc bien NP-complet.

12.1.5 Autour de SOMME DE SOUS-ENSEMBLE

D nition 12.11 (SOMME DE SOUS-ENSEMBLE)

Donn e: Un ensemble ni dentiers E et un entier t.

R ponse: D cider sil existe E(cid:48) E tel que (cid:80)

xE(cid:48) x = t.

Th or me 12.9 Le probl me SOMME DE SOUS-ENSEMBLE est NP-complet.

D monstration : Le fait que SOMME DE SOUS-ENSEMBLE est dans NP vient

du fait que la donn e de E(cid:48) constitue un certicat v riable en temps polynomial.

On va maintenant r duire une version de RECOUVREMENT DE SOMMETS dans

laquelle on cherche construire une couverture de taille exactement k SOMME DE

SOUS-ENSEMBLE. Il est facile de voir que cette version de RECOUVREMENT DE

SOMMETS est essentiellement quivalente la version classique, car il suft de d ci-

der pour chaque l d l0 sil existe une couverture de taille l pour savoir sil existe une

couverture de taille au plus l0.

On se donne un graphe G = (V, E) dans lequel on souhaite construire un recou-

vrement de sommets de taille k. On num rote les sommets et ar tes ; soit B = (bij) la

matrice dincidence sommets-ar tes, cest- -dire que bij = 1 si lar te i est incidente

au sommet j, bij = 0 sinon.

On va construire un ensemble F dentiers, tel que chaque sommet corresponde

un entier de F . On veut pouvoir lire sur la somme des l ments dun sous-ensemble les

ar tes dont un des sommets au moins appartient au sous-ensemble, de fa on ce quon

ait bien une couverture de sommets si et seulement si cest le cas pour toutes les ar tes.

Cela peut se faire en exprimant les entiers dans une base b xer ult rieurement, et

en faisant correspondre au sommet sj lentier (cid:80) bijbi. On veut aussi pouvoir compter

le nombre de sommets pr sents dans la couverture, qui doit tre gal k ; pour ce faire,

il suft dajouter un terme bn, si les ar tes sont num rot es de 0 n 1.

Il subsiste une difcult : pour quun sous-ensemble de somme t = (cid:80)n

i=0 aibi

corresponde une couverture de sommets, le choix que lon vient juste de faire impose

que (noter que tous les ai sauf an valent au plus 2, car une ar te est incidente deux

sommets exactement) :

an = k ;

ai e 1.

Les sp cications du probl me ne permettent pas de prendre en compte le second

item. On peut contourner le probl me en ajoutant F les entiers bi correspondant

lar te i.

10

CHAPITRE 12. QUELQUES PROBL MES NP-COMPLETS

On peut alors choisir comme but

t = kbn +

n1

(cid:88)

i=0

2bi.

(12.1)

ce stade, on va imposer que la base b soit au moins gale 4 ; comme dans

toute somme d l ments de F il y a au plus trois termes bi pour i < n, cela entra ne

quaucune retenue ne peut se produire dans laddition (on permet toujours au coef-

cient de bn dexc der b 1), et donc que lon peut lire sur l quation (12.1) le nombre

doccurrences du terme bi.

Pour tout sous-ensemble F (cid:48) de somme t, on a donc :

il y a k termes correspondant des sommets dans F (cid:48) (cf. le terme en bn pour

chaque ar te i) ;

F (cid:48) contient au moins un terme correspondant une des deux extr mit s de i ;

en effet, t contenant 2 termes bi, il peut contenir soit les deux extr mit s de

lar te, soit lentier correspondant lar te et celui correspondant lune des

deux extr mit s.

Inversement, tant donn e une couverture de sommets, on construit lensemble F (cid:48)

en prenant les sommets de la couverture, et les ar tes dont un seul des deux sommets

est dans la couverture.

On a donc bien r duit RECOUVREMENT DE SOMMETS SOMME DE SOUS-

ENSEMBLE.

Il est facile de voir que la r duction seffectue en temps polynomial, et donc que

(cid:3)

lon a bien prouv le th or me.

On peut en d duire :

D nition 12.12 (SAC A DOS)

Donn e: Un ensemble de poids a1, , an, un ensemble de valeurs v1, , vn,

un poids limite A, et un entier V .

R ponse: D cider sil existe E(cid:48) {1, 2, , n} tel que (cid:80)

iE(cid:48) ai d A et (cid:80)

iE(cid:48) vi e

V .

Corollaire 12.4 Le probl me SAC A DOS est NP-complet.

D monstration : A partir de SOMME DE SOUS-ENSEMBLE : tant donn e E =

{e1, , en} et t une instance de SOMME DE SOUS-ENSEMBLE, on consid re vi =

(cid:3)

ai = ei, et V = A = t.

D nition 12.13 (PARTITION)

Donn e: Un ensemble ni dentiers E.

R ponse: D cider sil existe E(cid:48) E tel que (cid:80)

xE(cid:48) x = (cid:80)

x(cid:54)E(cid:48) x.

Th or me 12.10 Le probl me PARTITION est NP-complet.

D monstration : On va r duire SOMME DE SOUS-ENSEMBLE PARTITION.

xE x.

Soit (E, t) une instance de SOMME DE SOUS-ENSEMBLE. On pose S = (cid:80)

12.2. EXERCICES

11

Quitte changer t en S t (ce qui revient changer lensemble obtenu en son com-

pl mentaire), on peut supposer que 2t d S.

Lid e naturelle consisterait ajouter l l ment u = S 2t E ; le r sultat de

partition serait alors deux sous-ensembles (A(cid:48) et son compl mentaire) de somme S t ;

lun des deux contient l l ment S 2t, donc en enlevant ce dernier, on trouve un

ensemble de termes de E de somme t. Malheureusement, cette technique choue si

S 2t est d j dans E.

Au lieu de cela, on prend le nombre X = 2S et X (cid:48) = S + 2t, et on applique

PARTITION E(cid:48) = E * {X, X (cid:48)}. Il existe une partition de E(cid:48) si et seulement sil

existe un sous-ensemble de E de somme t. En effet, sil existe une partition de E(cid:48),

il existe deux sous-ensembles compl mentaires de somme 2S + t. Chacun des deux

sous-ensembles doit contenir soit X, soit X (cid:48), car sinon sa somme ne peut exc der

2S + t ; donc un des deux ensembles contient X et non X (cid:48), et on obtient en enlevant

X un sous-ensemble F de E de taille t. R ciproquement, tant donn un tel F , (F *

{X}, E F * {X (cid:48)}) constitue une partition de E(cid:48). On a donc bien r duit SOMME

DE SOUS-ENSEMBLE PARTITION.

Reste justier que la r duction est bien polynomiale. Lessentiel de la r duction

est le calcul de A et A, qui est bien polynomial en la taille des entr es (laddition de k

(cid:3)

nombres de n bits se fait en temps O(k log n)).

12.2 Exercices

12.2.1 Variantes polynomiales

Exercice 12.1. Un graphe G = (V, E) est dit Eul rien sil existe un cycle empruntant

exactement une fois chaque ar te du graphe G.

Montrer quun graphe connexe est Eul rien si et seulement si chacun de ses som-

mets a un degr e pair.

Proposer un algorithme polynomial qui d termine si le graphe est Eul rien.

Exercice 12.2.

On sint resse 2SAT.

1. Proposer une valuation t qui satisfait 1(u1, u2, u3) = (u2 ( u3) ' ( u2 (

u3) ' (u2 ( u1).

2. Que se passe-t-il pour 2(u1, u2) = (u2 ( u3) ' ( u2 ( u3) ' ( u3 ( u1) '

( u3 ( u1) ?

3. Montrer que u ( v = ( u v) ' ( v u).

A partir dune instance de 2SAT nous construisons un graphe orient G =

(V, E) avec

un sommet par litt ral

et un arc par implication (en transformant chaque clause par deux implica-

tions)

4. Dessiner les graphes G 1 et G 2.

12

CHAPITRE 12. QUELQUES PROBL MES NP-COMPLETS

5. Montrer quil existe une variable u telle que G contient un cycle entre u vers

u dans G, si et seulement si nest pas satisable.

6. Montrer que 2-SAT peut se r soudre en temps polynomial.

Etant donn s n chevaliers, et connais-

Exercice 12.3.

sant toutes les paires de f roces ennemis parmi eux, est-il possible de les placer autour

dune table circulaire de telle sorte quaucune paire de f roces ennemis ne soit c te

c te ?

12.2.2 NP-compl tude

Exercice 12.4.

D nition : une cha ne hamiltonienne est une cha ne qui passe une fois et une seule

par chaque sommet du graphe.

Prouver que le probl me suivant est NP-complet.

CHAINE HAMILTONIENNE

Donn es : un graphe non-orient G de n sommets, deux sommets u et v distincts de G.

Question : G contient-il une chaine hamiltonienne dont ses extr mit s sont les sommets

u et v ?

Exercice 12.5. Prouver que le probl me suivant est NP-complet.

CHA NE

Donn es : un graphe non-orient G de n sommets, deux sommets u et v distincts de G.

Question : G contient-il une chaine de longueur n/2 entre u et v ?

Exercice 12.6. Prouver que le probl me suivant est NP-complet.

Probl me ARBRE

Donn es : Un graphe G = (V, E), et un entier k.

Question : Existe-t-il un arbre couvrant tous les sommets de G ayant moins de k

feuilles ?

Exercice 12.7. Soit G = (V, E) un graphe.

Une couverture de sommets S du graphe G est un sous-ensemble de sommets tel

que toutes les ar tes de G sont incidentes au moins un sommet de S.

Un ensemble dominant C du graphe G est un sous-ensemble de sommets tel que

tout sommet est soit dans C soit voisin dun sommet de C.

Soit G = (V, E) un graphe connexe. Nous allons construire un graphe G(cid:48) =

(V (cid:48), E(cid:48)) partir de G tel que

V (cid:48) = V * E ;

E(cid:48) = E * {(v, a)|v V, a E, v est extremit de lar te a dans G}

1. Montrer que si S est une couverture de sommets du graphe G, alors S est un

ensemble dominant de G(cid:48).

12.3. NOTES BIBLIOGRAPHIQUES

13

Graphe G

Graphe G(cid:48) (sans les ar tes de G)

2. Montrer que si S(cid:48) est un ensemble dominant de G(cid:48), alors il existe une couverture

S V du graphe G et de cardinalit inf rieure ou gale S(cid:48).

3. Exprimer le probl me de minimisation de lensemble dominant sous forme de

probl me de d cision.

4. Montrer que ce probl me est dans NP.

5. Montrer que ce probl me est dans NP-complet.

Exercice 12.8. Nous allons nous concentrer sur le probl me du k-centre : tant donn

un ensemble de villes dont les distances sont sp ci es, choisir k villes an dinstaller

des entrep ts de fa on minimiser la distance maximale dune ville lentrep t le plus

proche. Un tel ensemble de k villes est appel k-centre.

Le probl me associ de d cision est le suivant :

Probl me k-CENTRE

Donn es : un graphe complet K = (V, E) muni dune fonction de poids w sur les

ar tes, et des entiers strictement positifs k et b.

Question : Existe-il un ensemble S de sommets tel que |S| = k et tel que tout sommet

v de V satisfait la condition suivante

min{w(v, u) : u S} d b

1. Montrer que k-CENTRE est dans NP.

2. Montrer que k-CENTRE est NP-complet sachant que DOMINANT est NP-complet.

12.3 Notes bibliographiques

Lectures conseill es Le livre recense plus de 300 pro-

bl mes NP-complets et est dune lecture assez agr able. On peut trouver plusieurs

mises jour de cette liste sur le web.

Bibliographie Ce chapitre est repris du polycopi du cours INF550

de l cole polytechnique.

svuzt123456svuzt654321Index

(Ag, r, Ad), voir arbre binaire

(V, E), voir graphe

(q, u, v), voir conguration dune machine

de Turing

., voir concat nation

Ac, voir compl mentaire

F (G/p), voir substitution

L(M ), voir langage accept par une ma-

chine de Turing

, voir double implication

, voir d nition inductive / diff rentes

notations dune, voir implica-

tion

, voir alphabet

, voir ensemble des mots sur un alpha-

bet

), voir intersection de deux ensembles

*, voir union de deux ensembles

(cid:15), voir mot vide

a, voir quivalence entre formules, voir

quivalence entre probl mes

, voir quanticateur

, voir quanticateur

dm, voir r duction

|w|, voir longueur dun mot

d, voir r duction

P(E), voir parties dun ensemble

|=, voir cons quence s mantique

, voir n gation

(cid:54)|=, voir cons quence s mantique

, voir partie dun ensemble

, voir produit cart sien de deux ensembles

(cid:96), voir d monstration, voir relation suc-

cesseur entre congurations dune

machines de Turing

uqv, voir conguration dune machine de

Turing

(cid:104)(cid:104)M (cid:105), w(cid:105), voir codage dune paire

(cid:104)M (cid:105), voir codage dune machine de Tu-

ring

(cid:104)m(cid:105), voir codage

(cid:104) (cid:105), voir codage dune formule

(cid:104)w1, w2(cid:105), voir codage dune paire

2-SAT, 2

3-COLORABILITE, 7

3-SAT, 1

Arith, voir expressions arithm tiques

Arith(cid:48), voir expressions arithm tiques pa-

renth s es

circuit

hamiltonien dun graphe, 5

CIRCUIT HAMILTONIEN, 5

CIRCUIT LE PLUS LONG, 7

CLIQUE, 3

codage

notation, voir (cid:104).(cid:105)

dune formule

notation, voir (cid:104) (cid:105)

dune machine de Turing

notation, voir (cid:104)M (cid:105)

dune paire

notation, voir (cid:104)(cid:104)M (cid:105), w(cid:105), voir (cid:104)w1, w2(cid:105)

coloriage dun graphe, 7

compl mentaire

notation, voir Ac

du probl me de larr t des machines

de Turing

notation , voir HALTING PROBLEM

(, voir disjonction

', voir conjonction

compl tude

RE-compl tude, voir RE-complet

14

INDEX

concat nation

notation, voir .

15

de larr t des machines de Turing

notation, voir HALTING PROBLEM

conguration dune machine de Turing

notation, voir (q, u, v), voir uqv

COUPURE MAXIMALE, 4

produit cart sien

de deux ensembles

notation, voir

quivalence

entre probl mes

notation, voir a

graphe

R, voir d cidable

RE, voir r cursivement num rable

RECOUVREMENT DE SOMMETS, 4

r cusivement num rable

notation, voir RE

notation, voir (V, E)

r duction

HALTING PROBLEM, voir probl me

de larr t des machines de Tu-

ring

HALTING PROBLEM, voir compl -

mentaire du probl me de larr t

dune machine de Turing

intersection de deux ensembles

notation, voir )

langage

notation, voir d, voir dm

relation successeur entre congurations dune

machine de Turing

notation, voir (cid:96)

SAC A DOS, 10

SAT, 1, 2

satisfaction

dune formule, 1

SOMME DE SOUS-ENSEMBLE, 9

STABLE, 3

accept par une machine de Turing

notation, voir L(M )

union de deux ensembles

notation, voir *

VOYAGEUR DE COMMERCE, 6

longueur dun mot

notation, voir |w|

mot

vide

notation, voir (cid:15)

NAE3SAT, 2

NAESAT, 2

nombre chromatique dun graphe, 7

NP, 1

NP-compl tude, 17, 9, 10

partie

dun ensemble

notation, voir

parties

dun ensemble

notation, voir P(E)

PARTITION, 10

probl me

16

INDEX

Bibliographie

Cori, R., Hanrot, G., Kenyon, C., and Steyaert, J.-M. (2010).

Conception et analyse dalgorithmes. Cours de lEcole Polytechnique.

Garey, M. R. and Johnson, D. S. (1979). Computers and

Intractability. W. H. Freeman and Co.

17