Quelques problèmes NP-complets

SOMMETS à ce problème.

La technique consiste à construire, partant d’une instance de RECOUVREMENT DE SOMMETS, un graphe dans lequel chaque arête initiale sera remplacée par un “motif” admettant exactement deux chemins hamiltoniens, c’est-à-dire des chemins visitant une fois et une seule chaque sommet. L’un de ces deux chemins correspondra au cas où le sommet correspondant appartient à la couverture, l’autre au cas où il n’y appartient pas.

Il reste ensuite à préciser comment recoller ces différents motifs pour qu’un circuit hamiltonien global corresponde exactement à une réunion de chemins hamiltoniens à travers chaque motif, et pour assurer qu’on 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) l’instance 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 l’autre) ; 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 finie, 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 s’ensuit que si h est du côté de u, h sera atteint une fois au moins. On voit en vertu du second item qu’il ne sera plus atteint dans la suite. Si h est du côté de v, et que v n’est 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 l’on dispose d’un circuit hamiltonien de H. La construction de notre motif impose que venant d’un sommet si, on traverse entièrement une chaîne u puis l’on 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 d’une boucle correspondant à une des deux extrémités de l’arête.

donc bien NP-complet.

Enfin, 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éfinition 12.8 (VOYAGEUR DE COMMERCE)

Donnée: Un couple (n, M ), où M est une matrice n × n d’entiers et un entier k. Réponse: Décider s’il existe une permutation π de [1, 2, · · · , n] telle que

(cid:88)

1≤i≤n

Mπ(i)π(i+1) ≤ 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 d’un 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 d’entiers 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). S’il existe un circuit hamiltonien dans G on peut en effet construire la permutation π comme décrivant l’ordre 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 n−1 termes de la somme soient au moins égaux à 1 implique qu’ils 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éfinition 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 s’il existe un circuit de G ne passant pas deux fois par le même

sommet dont la longueur est ≥ 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 d’un cycle hamiltonien est alors trivialement identique à (cid:3) la recherche d’un circuit de longueur ≥ n dans le graphe.

12.1.4 Autour de 3-COLORABILITE

Nous avons déjà définit ce que nous appelions un (bon) coloriage de graphes dans le chapitre précédent. Le plus petit entier k tel qu’un 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éfinition 12.10 (3-COLORABILITE)

Donnée: Un graphe G = (V, E) non-orienté. Réponse: Décider s’il 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 certificat vérifiable 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 d’une part, et les règles d’évaluation d’une clause d’autre 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 qu’ils 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 qu’une 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 d’une 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 l’est, et la variable correspondante est coloriée V RAI.

Réciproquement, si l’une 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 d’une 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.

L’existence d’une 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éfinition 12.11 (SOMME DE SOUS-ENSEMBLE)

Donnée: Un ensemble fini d’entiers E et un entier t. Réponse: Décider s’il existe E(cid:48) ⊂ E tel que (cid:80)

x∈E(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 certificat vérifiable 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 suffit de déci- der pour chaque l ≤ l0 s’il existe une couverture de taille l pour savoir s’il 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 d’incidence sommets-arêtes, c’est-à-dire que bij = 1 si l’arête i est incidente au sommet j, bij = 0 sinon.

On va construire un ensemble F d’entiers, tel que chaque sommet corresponde à un entier de F . On veut pouvoir lire sur la somme des éléments d’un sous-ensemble les arêtes dont un des sommets au moins appartient au sous-ensemble, de façon à ce qu’on ait bien une couverture de sommets si et seulement si c’est le cas pour toutes les arêtes. Cela peut se faire en exprimant les entiers dans une base b à fixer ultérieurement, et en faisant correspondre au sommet sj l’entier (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 suffit d’ajouter un terme bn, si les arêtes sont numérotées de 0 à n − 1.

Il subsiste une difficulté : pour qu’un sous-ensemble de somme t = (cid:80)n i=0 aibi corresponde à une couverture de sommets, le choix que l’on 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 ≥ 1. Les spécifications 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 à l’arête i.

10

CHAPITRE 12. QUELQUES PROBLÈMES NP-COMPLETS

On peut alors choisir comme but

t = kbn +

n−1 (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 qu’aucune retenue ne peut se produire dans l’addition (on permet toujours au coeffi- cient de bn d’excéder b − 1), et donc que l’on peut lire sur l’équation (12.1) le nombre d’occurrences 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 l’arête, soit l’entier correspondant à l’arête et celui correspondant à l’une des deux extrémités.

Inversement, étant donnée une couverture de sommets, on construit l’ensemble 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 s’effectue en temps polynomial, et donc que (cid:3)

l’on a bien prouvé le théorème.

On peut en déduire :

Définition 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 s’il existe E(cid:48) ⊂ {1, 2, · · · , n} tel que (cid:80)

i∈E(cid:48) ai ≤ A et (cid:80)

i∈E(cid:48) vi ≥

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éfinition 12.13 (PARTITION)

Donnée: Un ensemble fini d’entiers E. Réponse: Décider s’il existe E(cid:48) ⊂ E tel que (cid:80)

x∈E(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. x∈E 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 l’ensemble obtenu en son com- plémentaire), on peut supposer que 2t ≤ S.

L’idé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 ; l’un 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 s’il existe un sous-ensemble de E de somme t. En effet, s’il 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 à justifier que la réduction est bien polynomiale. L’essentiel de la réduction est le calcul de A et A’, qui est bien polynomial en la taille des entrées (l’addition 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 s’il existe un cycle empruntant exactement une fois chaque arête du graphe G.

Montrer qu’un 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 s’inté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 d’une 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 qu’il existe une variable u telle que Gφ contient un cycle entre u vers

¬u dans G, si et seulement si φ n’est pas satisfiable.

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

[Chevaliers de la table ronde] 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 d’une table circulaire de telle sorte qu’aucune paire de féroces ennemis ne soit côte à côte ?

12.2.2 NP-complétude

Exercice 12.4.

Définition : 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 d’un 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 l’arê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 l’ensemble 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écifiées, choisir k villes afin d’installer des entrepôts de façon à minimiser la distance maximale d’une ville à l’entrepô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 d’une 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} ≤ 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 [Garey and Johnson, 1979] recense plus de 300 pro- blèmes NP-complets et est d’une lecture assez agréable. On peut trouver plusieurs mises à jour de cette liste sur le web.

Bibliographie Ce chapitre est repris du polycopié [Cori et al., 2010] du cours INF550 de l’école polytechnique.

svuzt123456svuzt654321Index

(Ag, r, Ad), voir arbre binaire (V, E), voir graphe (q, u, v), voir configuration d’une 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éfinition inductive / différentes notations d’une, 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 ≡, voir équivalence entre formules, voir

équivalence entre problèmes

∃, voir quantificateur ∀, voir quantificateur ≤m, voir réduction |w|, voir longueur d’un mot ≤, voir réduction P(E), voir parties d’un ensemble |=, voir conséquence sémantique ¬, voir négation (cid:54)|=, voir conséquence sémantique ⊂, voir partie d’un ensemble ×, voir produit cartésien de deux ensembles (cid:96), voir démonstration, voir relation suc-

cesseur entre configurations d’une machines de Turing

uqv, voir configuration d’une machine de

Turing

(cid:104)(cid:104)M (cid:105), w(cid:105), voir codage d’une paire (cid:104)M (cid:105), voir codage d’une machine de Tu-

ring

(cid:104)m(cid:105), voir codage (cid:104)φ(cid:105), voir codage d’une formule (cid:104)w1, w2(cid:105), voir codage d’une 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 d’un graphe, 5

CIRCUIT HAMILTONIEN, 5 CIRCUIT LE PLUS LONG, 7 CLIQUE, 3 codage

notation, voir (cid:104).(cid:105) d’une formule

notation, voir (cid:104)φ(cid:105) d’une machine de Turing notation, voir (cid:104)M (cid:105)

d’une paire

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

coloriage d’un graphe, 7 complémentaire

notation, voir Ac du problème de l’arrê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 l’arrêt des machines de Turing

notation, voir HALTING − PROBLEM

configuration d’une 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 ≡

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 l’arrêt des machines de Tu- ring

HALTING − PROBLEM, voir complé- mentaire du problème de l’arrêt d’une machine de Turing

intersection de deux ensembles

notation, voir ∩

langage

notation, voir ≤, voir ≤m

relation successeur entre configurations d’une

machine de Turing

notation, voir (cid:96)

SAC A DOS, 10 SAT, 1, 2 satisfaction

d’une 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 d’un mot

notation, voir |w|

mot

vide

notation, voir (cid:15)

NAE3SAT, 2 NAESAT, 2 nombre chromatique d’un graphe, 7 NP, 1 NP-complétude, 1–7, 9, 10

partie

d’un ensemble

notation, voir ⊂

parties

d’un ensemble

notation, voir P(E)

PARTITION, 10 problème

16

INDEX

Bibliographie

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

Conception et analyse d’algorithmes. Cours de l’Ecole Polytechnique.

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

Intractability. W. H. Freeman and Co.

17