U-Psud, L3 Math, L3-M1 Info Informatique Théorique

Feuille de TD N o1 Automates

1. Donnez des automates reconnaissants :

• les mots commençant par aabab

• les mots contenant abbab
• les mots finissant par abaaba
• les représentations en binaire des multiples de 5
• les mots sur {a, b, c} ayant un nombre pair de a, pair de b et pair de c.
• les mots dont l’avant-avant-avant-dernire lettre est un b.

2. Soit deux automates déterministes A et B.

Donner un algo en lecture-simple-et-oubli et à mémoire finie, qui détecte si un mot est dans
L(A) ∩ L(B).
En déduire la construction d’un automate pour L(A) ∩ L(B).
Combien d’états a ce nouvel automate ?
Utilisez cette construction pour obtenir un automate déterministe reconnaissant les mots sur
{a, b} ayant un nombre pair de a et contenant ab.
Que pouvez-vous faire pour des automates non-déterministes ?
Peut-on utiliser cette méthode pour l’union ?

3. Soit un automate non-déterministe A. Donner un algo en lecture-simple-et-oubli et à mémoire

finie, qui détecte si un mot est dans L(A). En déduire la construction d’un automate déterministe
pour L(A).
Combien d’états a ce nouvel automate ?

4. Determininisez :  
2  b

a a a
 


? 

? a, b  a  b 
? 
a - 
1 a
- 1

- 2

- 3k

- 4


a@
I
@

?
3  b
6
&
a, b % 

5. Soit L = {an bn | n ∈ IN }.
Pour chaque mot u ∈ {a, b}∗ , donnez F uturL (u).
Supposons qu’un automate déterministe AL reconnaisse L. Soit p < q, les mots ap b et aq b
peuvent-ils conduire au même état depuis q0 ? Le langage L est-il reconnaissable ?
6. Minimisez :
a a 
  a 7 - 8l - 9l 
   
a
     ? ? 6@ b a
6
- 1l a- 2 a- 3 a- 4 a- 5 b @
b@ ? a b
      @ R 
?

b 6 @b ?
@
b b 4l - 5 6 a
b b  a  
@ R 
?
6  7l 
6b b
a
6
a 8 b a
  a, b 
b  ?
a 
?

3l 
6 - 1 - 2  -
b  b 

7. Un automate boustrophédon est un automate dans lequel on peut se déplacer à gauche et à

droite. On supposera qu’avant et après le mot, il y a respectivement un |> et un <| avec
interdiction d’aller à gauche du premier et à droite du second. Les transitions sont donc
indexées par une lettre lue mais aussi par un sens de déplacement G ou D. Un mot est accepté
s’il existe une exécution qui s’arrête en état final. Montrez qu’un langage reconnu par un
automate boustrophédon est reconnaissable par un automate classique.

8. Le barman aveugle avec des gants de boxe ...

Un barman et un client jouent au jeu suivant :
Le barman met un bandeau sur les yeux qui le rend aveugle, et il met des gants de boxe qui
l’empêchent de ”sentir” si un verre est à l’endroit ou à l’envers.
Devant le barman, se trouve un plateau tournant sur lequel sont placés quatre verres en carré.
Ces verres peuvent être à l’envers ou à l’endroit. Le sens initial des verres est choisi par le
client et est inconnu du barman.
Si les verres sont tous dans le même sens, alors le barman gagne (Quand le barman gagne, un
autre client, ”arbitre”, annonce qu’il a gagné et le jeu s’arrête.)
Le barman peut répéter l’opération suivante : Il annonce au client qu’il va retourner certains
verres (par exemple le verre en bas à gauche et celui en bas à droite). Le client fait alors tourner
le plateau, puis le barman retourne les verres comme il l’a annoncé. Si les verres sont alors tous
dans le même sens, le barman gagne.

1) On se place du point de vue du client. Donnez un automate dont les états sont les différentes
configurations du plateau, les lettres les coups annoncés par le barman et où les flèches decrivent
les évolutions possibles des configurations.

2) Donnez un automate non déterministe (avec éventuellement plusieurs états entrée) qui donne
toutes les séquences d’annonces du barman pour lesquelles le client peut gagner (à condition
de toujours faire les bons choix).

3) Donnez un automate qui donne les coups qui assurent au barman de gagner quel que soit le
comportement du client.

4) Jouez-vous de l’argent contre le barman ?

5) Et si au lieu de 4 verres, il y a 3 verres en triangle ou bien 5 verres en pentagone ? S’il y a

n verres disposés en polygone régulier ?
 Feuille de TD N o2 Machines de Turing

1. Donnez des machines de Turing qui reconnaissant l’ensemble P des palindromes (sur deux lettres)

• Sur deux bandes, déterministe. Quelle est la complexité ?

• Sur deux bandes, non déterministe, avec une complexité en temps N + O(1)
• Sur une bande, déterministe. Quelle est la complexité ? Dans quelle mesure arrivez-vous à
améliorer cette complexité ?
• Sur plusieurs bandes, avec une complexité en espace en θ(ln(N )). Quelle est la complexité en
temps ?
• Sur plusieurs bandes, non déterministe, qui reconnait CP le complémentaire de P , avec une
complexité en espace en θ(ln(N )) et une complexité en temps linéaire.

2. Montrez qu’un calcul peut être fait sur une machine à deux bandes ssi il peut être fait sur une machine
à une bande. Quelle répercussion le changement de modèle a-t-il sur la complexité en temps ?

3. MTD pour faire le schéma de récurrence

On dira que la machine M à K + T + 1 bandes calcule proprement la fonction f de IN k dans IN ssi
• M calcule f
• Les K premières bandes (les ”bandes d’entrée”) sont en lecture seulement (c.a.d. ne sont jamais
modifiées).
• La dernière bande (la ”bande de sortie”) est en écriture seulement, c.a.d. que l’action de toute
transition sur cette bande est, soit de rester immobile sans modifier le contenu de la case, soit d’écrire
autre chose qu’un espace dans la case de cette bande et de se déplacer à droite.
• Quand un calcul se termine, à la fin du calcul, les T bandes centrales (les ”bandes de travail”) ne
contiennent que des espaces.
• Quand un calcul se termine, les pointeurs de toutes les bandes, sauf la dernière, sont ramenés en
tête de bande.
Si g et h sont des fonctions de IN q−1 dans IN et de IN q+1 dans IN respectivement, alors on définit
SchemaDeRecurrenceg,h de IN q dans IN comme suit :
SchemaDeRecurrenceg,h (x1 , ..., xq−1 , y) = si y = 0 alors g(x1 , ..., xq−1 )
sinon h(x1 , ..., xq−1 , y − 1, SchemaDeRecurrenceg,h (x1 , ..., xq−1 , y − 1))
On suppose que g et h sont calculables proprement par des machines Mg et Mh avec Tg et Th bandes
de travail, Donnez la construction d’une machine qui calcule proprement SchemaDeM inimisationg,h
à partir de Mg et de Mh . Soyez précis dans la description et donner le nombre de bandes de travail
de votre construction (soyez économe). Note: Il vous est demandé de ne pas utiliser les constructions
vues en cours pour rassembler plusieurs bandes sur une seule, qui sont trop coûteuses en complexité
en temps.
 Informatique Théorique : TD N o 3 : Décidabilité,
semi-décidabilité, indécidabilité

1 Décidables et semi-décidables
(1) Parmi les problèmes suivants, lesquels sont décidables, semi-décidables, co-semi-décidables ?
Tri(T) : Est-ce que le tableau T est trié.
Equiv(A1,A2) : Est-ce que les deux automates A1 et A2 reconnaissent le même language.
Inters(G1,G2) : Est-ce que les langages des deux grammaires G1 et G2 ont au moins un mot en commun.
Arrêt(M,u) : Est-ce que la machine de Turing M s’arrête sur l’entrée u.
NonArrêt(M,u) : Est-ce que la machine de Turing M ne s’arrête pas sur l’entrée u.
TimeArrêt(M,u,T) : Est-ce que la machine de Turing M s’arrête sur l’entrée u en un temps au plus T.
Racine(P) : Est-ce que le polynome P à une variable avec des coefficients entiers, a une racine dans IN
RacineBis(P) : Est-ce que le polynome P à plusieurs variables x1 , x2 , x3 , .., xp avec des coefficients entiers, a
un système de racine r1 , r2 , r3 , .., rp dans IN p
ArrêtIlExiste(M) : Est-ce que la machine de Turing M s’arrête sur au moins une entrée.
ArrêtPourTout(M) : Est-ce que la machine de Turing M s’arrête sur toutes les entrées.
Π1D (x) : existe-t-il un (entier) y tel que D(x,y) où D est supposé être décidable.
Π2D (x) : existe-t-il un y tel que pour tout z, on a D(x, y, z) où D est décidable.

(2) Si A et B sont décidables, en est-il de même pour A ∩ B ? pour A ∪ B ? Mêmes questions avec
semi-décidables. Qu’en est-il de la stabilité par complémentaire ? Qu’en est-il pour P, NP, Pspace ?

(3) Lien entre fonction et graphe de cette fonction

Pour toute fonction partielle f de IN dans IN , on note Gf son graphe, ie Gf = {(x, y)|y = f (x)}
(3a) Si f est totale et calculable, que peut-on en déduire pour Gf ? Est-il décidable ? semi-décidable ?
(3b) Si f est calculable, que peut-on en déduire pour Gf ? Est-il décidable ? semi-décidable ?
(3c) Si Gf est décidable, que peut-on en déduire pour f ? Est-elle calculable ? calculable et totale ?
(3d) Si Gf est semi-décidable, que peut-on en déduire pour f ? Est-elle calculable ? calculable et totale ?

(4) le mot u est facteur du mot v ssi il existe x et y tel que v = xuy. Il en est un sous-mot ssi on peut
obtenir u en effaçant des lettres dans v. Exemples, abcd,  et bc sont facteurs donc sous-mots de abcd. ac est
en sous-mot mais pas facteur. Si L est un langage, on note F acteurs(L) = {v | ∃u ∈ L, v est facteur de u}
l’ensemble de ses facteurs. De façon similaire, on aura ReverseFacteurs(L), SousMots(L), Surmots(L). Que
peut-on dire de ces ensembles si L est décidable, semi-décidable, P, NP, Pspace ?

2 Le problème de Post
Le problème de Post (abab, ab), (a, aa), (b, aba), (a, b) a-t-il une solution commençant par la première paire
?
Le probléme de Post (X, X000000p) (X, X) (0, 0), (1, 1) (0p, 1q), (1p, p0), (q0, 0q), (qX, pX), (Xp0, Xp),
(XpX, X) a-t-il une solution commençant par la première paire ?

3 Réductions
(1) On suppose que l’on a une réduction du problème X dans le problème Y , quelles sont les situations
possibles : (A) X et Y sont décidables. (B) ni X ni Y ne sont décidables. (C) X est décidable mais Y ne
l’est pas. (D) Y est décidable mais X ne l’est pas.
(2) Soit D un problème décidable, Donner une réduction de Π1D dans Arrêt.
Montrez plus généralement qu’il y a une réduction de tout problème semi-décidable dans Arrêt. On dira
que Arrêt est semi-dcidable-complet.
Montrez que pour tout problème semi-décidable X, il existe un ensemble décidable DX tel que Π1DX .
4 Rice
En génie logiciel, on cherche à vérifier que les programmes vérifient certaines propriétés, dites ”spécifications”.
Une spécification fonctionnelle repose uniquement sur la fonction produite par la machine, et non sur
son fonctionnement interne. Par exemple, ”la machine rend un entier non nul sur les entrées paires et ne
rend pas de résultat sur les entrées impaires” est une spécification fonctionnelle. Par contre, ”la machine
est de complexité polynomiale” ou bien, ”il existe une entrée qui engendre une exécution qui passe par tous
les états de la machine” ne sont pas des spécifications fonctionnelles.
Une telle spécification est totalement décrite par le sous-ensemble X des fonctions partielles de IN dans
IN qui vérifient la propriété souhaitée. Savoir si une machine M vérifie la propriété souhaitée se ramène alors
au problème PX qui prend en entrée une machine de Turing M et demande si fM ∈ X, où fM désignera la
fonction réalisée par la machine M .
Exemples: Si Y est l’ensemble des fonctions totales, le problème PY demande si la machine en entrée
s’arrête sur toute entrée. Si prime est la fonction indicatrice des nombres premiers, alors le problème
P{prime} demande si la machine en entrée est une machine qui décide si son entrée est un nombre premier.

(1) Soit X1 = ∅, X2 l’ensemble de toutes les fonctions partielles de IN dans IN , et X3 l’ensemble de

toutes les fonctions partielles calculables. Est-ce que PX1 , PX2 et PX3 sont décidables ? Justifiez.

On suppose à partir de maintenant que X est un ensemble de fonction telle qu’il existe deux machines
Moui et Mnon avec fMoui ∈ X et fMnon 6∈ X (la machine Moui vérifie la spécif. tandis que Mnon ne la vérifie
pas).
On notera f∅ la fonction définie nulle part (Attention, ne confondez pas P∅ et P{f∅ } )
(2) On suppose pour cette question que f∅ 6∈ X. Pour toute machine M et toute entrée u, on note ΠM,u
la machine qui prend en entrée v, simule M sur u mais jette l’éventuel résultat à la poubelle PUIS simule
Moui sur v. Que vaut fΠM,u ? Est-ce que PX (ΠM,u ) ? Discutez en fonction de M et de u.
Montrez que PX est indécidable.
(3) Montrez que PX est également indécidable si f∅ ∈ X.

5 Indécidabilité de l’arrêt par la fonction Kolmogorov

On considère un langage de programmation X (qui peut être C, Pascal, Caml, ..., peu importe)
Soit A = {0, 1}. On note A∗ l’ensemble des mots sur A, i.e. des suites finies à valeur dans A. On note
|m| la longueur d’un mot m (Exemple, |0010110| = 7)
On Définit la fonction K qui à chaque mot m ∈ A∗ , associe la longueur en nombre de bits du plus court
programme X qui ne fait aucune lecture, qui termine, et ce après avoir eu comme effet d’écrire le mot m.

1. Montrez ∃D, H ∈ IN , ∀m ∈ A∗ , K(m) ≤ H ∗ |m| + D

2. Montrez qu’il existe une suite de mots (mi )i∈IN tq |mi | tende vers l’infini et K(mi ) = o(ln(ln(ln(|mi |)))))

3. Soit r un réel dans [0, 1[. Soit Xn un mot de longueur n aléatoire. Montrez que la probabilité que
K(Xn ) > m − 10 es inférieure à 0.1%

4. Montrez que si l’arrêt etait décidable, alors K serait calculable. Que peut-on en déduire pour la
calculabilite de K ?
On définit la fonction fK qui à n associe le plus petit mot m tq K(m) > n où, par définition, le mot
m1 est plus petit que le mot m2 ssi (il est plus court) ou (il est de même longueur, mais apparaı̂t
avant dans l’ordre alphabétique)

5. Montrez que si K est calculable, alors il existe des constantes G et L telle que pour tout n ∈ IN ,
K(fK (n)) ≤ G + L ∗ ln n (On rapelle que le nombre de bits pour écrire n en base 2 est environ ln2 n)

6. Montrez que K n’est pas calculable.

7. Donner une nouvelle démonstration de l’indécidabilité du problème de l’arrêt.

 Informatique Théorique : TD N o 4 : NP

6 Stabilités par permutation

On considère l’alphabet infini A = {a1 , a2 , a3 , ..., ai , ...} = (ai )i∈IN ∗ et l’ensemble X des mots finis à valeur
dans A.
(La lettre ai sera codée par i en binaire, et par exemple le mot a4 a1 a1 a11 pourra être codé par
$100$1$1$1011$. Cette remarque est d’un intérêt mineur)
On identifie les mots sur A et les suites finies à valeur dans IN . Ainsi le mot a6 a12 a6 a26 est identifié à
la suite finie (6,12,6,26).
Si E est sous-ensemble de X, on note P erm(E) l’ensemble des mots obtenus en permutant les lettres
de E.
Par exemple, si E = {a1 , a2 a2 , a4 a2 a7 , ...} = {(1), (2, 2), (4, 2, 7), ...} alors
perm(E) = {a1 , a2 a2 , a4 a2 a7 , a4 a7 a2 , a2 a4 a7 , a2 a7 a4 , a7 a4 a2 , a7 a2 a4 , ...}
= {(1), (2, 2), (4, 2, 7), (4, 7, 2), (2, 4, 7), (2, 7, 4), (7, 4, 2), (7, 2, 4), ...}.

(1) Soit F l’ensemble des suites finies strictement croissantes. Que vaut perm(F ) ?
(2) Soit G = {(u, M )|M sur u s’arrête } ∪ {(M, u)|M sur u ne s’arrête pas } (On rappelle que les ma-
chines M tout comme les entrées u sont identifiées à des entiers grâce à des codages en binaire). Est-ce que
G est décidable, semi-décidable, co-semi-décidable ? Justifiez proprement. Qu’en est-il de perm(G) ?
(3) Soit H = {(b1 , b2 , ..., bk , p, c1 , c2 , ..., cl ) | p est un entier supérieur ou égal à 2, b1 b2 ...bk est l’écriture
en base 2 d’un diviseur de p autre que p ou 1, les bi et les cj sont des 0 ou des 1, avec autant de 0 que de
1 que de chiffres dans l’écriture en base 2 de p. } Exemple : (1,1,0,1,1,0,1,327,1,0,0,1,0,1,0,0,0,0,1) ∈ H, car
1101101 en base 2, c’est 109, qui divise 327, et il y a 9 ”0”, 9 ”1”, et 327 s’écrit avec 9 chiffres en base 2.
Que vaut perm(H) ?
(4) Est-il vrai que si E est décidable, alors perm(E) est décidable ?
(5) Est-il vrai que si E est semi-décidable, alors perm(E) est semi-décidable ?
(6) Est-il vrai que si E est dans P, alors perm(E) est dans P ?
(7) Est-il vrai que si E est dans NP, alors perm(E) est dans NP ?

Pour les questions (4) à (7) en particulier, toute réponse non justifiée rapportera 0 points. Pour certaines
justifications, des arguments clefs sont attendus. Soyez soigneux et précis et ne passez pas à côté (ce qui
n’empêche pas que une ou deux phrases de justification peuvent parfois suffire à avoir les points du moment
qu’elles contiennent les points clefs).
Par ailleurs, il se peut que vous ayez un avis sur une des réponses sans que vous arriviez à démontrer
votre idée. Dans ce cas, dites ”je conjecture que” et expliquez ce qui motive votre conjecture.

7 SAT
• 3-SAT est le même problème que SAT, mais avec des clauses de 3 littéraux exactement. Montrez que
3-SAT est NP-complet

• SAT-GEN est le même problème que SAT, mais avec une formule logique pas nécessairement en forme
normale, utilisant tous les opérateurs logiques, les parenthésages imbriqués. Montrez que SAT-GEN
est NP-complet.

• Montrez qu’il y a une réduction polynomiale de SAT-GEN dans SAT. En donnez une explicite.

• SAT-SOLUCE dit si une formule est satisfiable, mais de plus, donne une solution si la formule est
satisfiable. Montrez que SAT-SOLUCE et SAT sont P-équivalents, ie que si on a un oracle pour l’un,
l’autre peut se faire en temps polynomial.

• SAT-CARD donne le nombre de solutions d’une formule. Essayez de comparer SAT et SAT-CARD.
Donnez un problème de décision qui est P-équivalent à SAT-CARD.
8 Cliques
Une clique d’un graphe G est un ensemble Y de sommets tous reliés deux à deux.
CLIQUEMAX(G) rend le cardinal maximum des cliques de G
CLIQUE(G,k) rend vrai ssi G possède une clique de taille k.
CLIQUE-SOLUCE rend de plus une clique s’il y en a une.
3-CLIQUE (G), resp 1000-CLIQUE(G) rend vrai ssi G possède une 3-CLIQUE, resp une 1000-CLIQUE.
• Dans quelle classe de complexité se trouvent 3-CLIQUE et 1000-CLIQUE ?
• Montrez que CLIQUEMAX, CLIQUE et CLIQUE-SOLUCE sont P-équivalents.
• Que pensez-vous de l’affirmation ”CLIQUEMAX est NP-complet” ?

Soit F une formule logique en forme normale. F = ∧Q Ki

i=1 Ci , Ci = ∨j=1 Li,j , Li,j des littéraux.
On construit le graphe GF comme suit :
SGF = {si,j | i ≤ Q ∧ j ≤ Ki }, AGF = {(si,j , sī,j̄ ) | i 6= ī ∧ Li,j n’est pas la négation de Lī,j̄ }
• Montrez que F est satisfiable ssi GF possède une clique de taille Q
• Montrez que CLIQUE est NP-complet

Une couverture d’un graphe G est un ensemble x de sommets tel que toute arête a au mois une extrêmité
dans X. COUV-MIN (G) rend le cardinal minimum des couvertures de G. COUV(G,k) rend vrai ssi G
possède une couverture de taille k
Un stable d’un graphe G est un ensemble x de sommets tel que toute arête a au plus une extrêmité
dans X. STABLE-MAX (G) rend le cardinal maximum des stables de G. STABLE(G,k) rend vrai ssi G
possède un stable de taille k.
• Etablir des liens entre les cliques, les stables et les couvertures.
• Montrez que COUV et STABLE sont NP-complets.

Un couplage de G est un ensemble d’arêtes sans extrêmités en commun. Il est maximal, resp. maximum
si on ne peut pas y ajouter une arête, resp. s’il contient le plus d’arêtes possible (max pour l’inclusion, resp.
pour le cardinal).
• Donnez un couplage maximal non maximum. Trouver un couplage maximal, resp. maximum est-il P ?
Soit Γ un couplage maximal, C l’ensemble des extrêmités de Γ, et Cmin une couverture minimum.
• Montrez que |Cmin | ≥ |Γ| et que C est une couverture. En déduire un ”algo polynomial d’approximation
de facteur 2” pour COUV.

9 HAM et VC
HAM(G) rend vrai ssi G possède un cycle hamiltonien.
VC-MIN(G) rend le poids minimum des cycles hamiltonien de G, graphe complet valué aux arêtes.
VC(G,k) rend vrai ssi il existe un cycle hamiltonien de poids k ou moins.
VC-IT est VC restreint aux graphes vérifiant l’inégalité triangulaire (∀x, y, z, w(xz) ≤ w(xy) + w(yz))
• HAM possède en fait deux variantes HAMO et HAMNO pour les graphes orientés et non-orientés.
Montrez qu’elles sont P-équivalentes.

Soit F = ∧i∈[1..Q] Ci une formule booléenne en forme normale sur les variables (Vr )r∈[1..W ] .
On construit le graphe GQ,W dont les sommets sont les (Lr,s )r∈[1..W ],s∈[1..3Q+3] et les arcs sont les
{(Lr,s , Lr,t ) | |s − t| = 1} ∪ {(Lr,s , Lr+1,t ) | s, t ∈ {1, 3Q + 3}} (avec ”r + 1 = 1” si r = W )
• Combien GQ,W a-t-il de cycles hamiltoniens ? Faire un lien avec les affectations des variables de F .
On construit GF en ajoutant à GQ,W les sommets (Ki )i∈[1..Q] et, si Vr , resp. ¬Vr , est littéral de Ci , on
ajoute les arcs (Lr,3i , Ki ) et (Ki , Lr,3i+1 ), resp. (Lr,3i+1 , Ki ) et (Ki , Lr,3i ).
• Montrez que si F est satisfiable alors GF est hamiltonien.
• Montrez que si un GF a un cycle hamiltonien passant par (Lr,3i , Ki ), alors il passe aussi par (Ki , Lr,3i+1 ).
• Montrez que HAM est NP-complet

• Montrez que VC est NP-complet

• Montrez que VC-IT est NP-complet
COURS : algos d’approximation pour VC-IT-MIN.
• Montrez qu’il n’existe pas d’algo d’approximation pour VC-MIN (à moins que P = N P )
10 NP-complétude de K-coloriage d’un graphe
Soit K un entier. Un graphe non-orienté G est K-coloriable ssi on peut colorier ses sommets avec K couleurs
ou moins de sorte que des sommets reliés ne sont jamais de la même couleur.
10.1 3-coloriage
Le but de cette partie est de montrer que 3-coloriable est NP-complet.
(1) Montrez que 3-coloriable est NP.
Soit F une formule booléenne sur les variables {V1 , ..., Vp }, F en forme normale, i.e. que F = ∧i∈[1..C] Ci ,
où les Ci sont les clauses avec pour chaque i, Ci = ∨j∈[1..ni ] Li,j . Les Li,j sont les littéraux, qui sont donc
une variable ou la négation d’une variable.
On construit alors un graphe GF , dont les sommets sont:
• 3 sommets V , F , N (initiales de Vrai, Faux Neutre)
• 2p sommets {V1vrai , V1f aux , V2vrai , V2f aux , ..., Vpvrai , Vpf aux } correspondants aux affectations des variables
• C sommets K1 , ..., KC correspondants aux clauses C1 , ..., CC
• D’autres sommets que vous serez amenés à introduire.
Vous définirez ce que sont les arêtes.
(2) on veut que les 3 sommets V , F et N ne puissent pas être coloriés autrement qu’avec 3 couleurs
différentes. Comment l’imposer ? On notera V ert, F auve et N oir les couleurs des sommets V , F et N
respectivement.
(3) On veut que pour chaque k et pour tout coloriage G, l’on ait (Vkvrai Vert et Vkf aux Fauve) ou (Vkvrai
Fauve et Vkf aux Vert). Comment le forcer ? (Vkvrai Vert et Vkf aux Fauve) est associé à l’affectation Vk ← vrai
tandis que (Vkvrai Fauve et Vkf aux Vert) est associé à l’affectation Vk ← f aux
(4) Donner toutes les manières de colorier le petit graphe ci-contre Am Xm
QQ m
de sorte que ni A, ni B, ni C ne soient Noir (mais X et Y peuvent l’être) C
Bm Ym
(5) On suppose que les sommets Vjb sont coloriés (ainsi que V , F et N ).
On veut à présent que, pour chaque i, l’on puisse colorier le sommet Ki en V ert ssi au moins un des
sommets Vqb associés aux littéraux de la clause Ci est V ert (exemple, si C7 = V2 ∨ ¬V3 ∨ V6 ∨ ¬V8 ∨ ¬V9 alors
K7 peut être colorié en V ert ssi au moins un des sommets V2vrai , V3f aux , V6vrai , V8f aux , V9f aux est V ert).
Comment le forcer ? Faire le dessin pour la clause C7 donnée en exemple.
(6) Terminer la construction de GF . Vérifier en quelques lignes que F → GF est une réduction polyno-
miale. En déduire que 3-Coloriable est NP-complet.

10.2 4-coloriage
(7) Montrez que 4-coloriable est NP-complet.
10.2.1 P-équivalences de variantes de 3-coloriage
(8) Soit G 3-coloriable et x et y deux sommets non reliés de G. A quelle condition sur les 3-coloriages de G
existe-t-il un 3-coloriage de G + (x, y) ?
(9) Montrez que les deux problèmes suivants sont polynomialement équivalents, i.e. que si l’on a un
oracle pour l’un, on peut résoudre l’autre en temps polynomial.
• Savoir si un graphe est 3-coloriable.
• Savoir si un graphe est 3-coloriable et si oui, fournir un 3-coloriage.

10.3 3-coloriage avec degrés inférieurs ou égaux à 5

(10) Montrez que 3-coloriable est toujours NP-complet si on le restreint aux graphes dont tous les sommets
sont de degré inférieur ou égal à 5 (Indication: dédoubler les sommets de degré 6 au plus, quitte à introduire
de nouveaux sommets)
(11) Montrez que 3-coloriable est toujours NP-complet si on le restreint aux graphes dont tous les
sommets sont de degré inférieur ou égal à 4.
i
10.4 3-coloriage des graphes planaires i i@ i
@
(12) Quels sont, à intervertion des couleurs près, les 3-coloriages du graphe:
i i i@ i@ i
@ @
Si l’on impose les couleurs du sommet en haut et de celui à gauche,
quelles couleurs peut-on avoir sur le sommet du bas et celui à droite ? @@i
@@i i
(13) Montrez que 3-coloriable est toujours NP-complet si on le @@i
restreint aux graphes planaires (i.e. que l’on peut dessiner sur un plan).
11 SAC A DOS
◦ SACADOS-1 prend en entrée une suite finie d’entiers (xi )i∈[1..N ] et un entier Γ et demande si il existe
P
une partie J de [1..N ] telle que i∈J xi = Γ.
◦ SACADOS-2 prend en entrée une suite finie d’entiers (xi )i∈[1..N ] et demande si il existe une partie J
P P
de [1..N ] telle que i∈J xi = i6∈J xi .
◦ SACADOS-3 prend en entrée une suite finie d’entiers ”valeurs” (vi )i∈[1..N ] , une suite finie d’entiers
”poids” (pi )i∈[1..N ] ; un poids P , et rend le maximum des i∈J vi restreint aux parties J vérifiant i∈J pi ≤ P
P P

◦ SACADOS-4 prend en entrée une suite finie d’entiers ”valeurs” (vi )i∈[1..N ] , une suite finie d’entiers
”poids” (pi )i∈[1..N ] ; un poids P , une valeur V et rend vrai ssi il existe une partie J telle que i∈J vi ≥ V et
P

i∈J pi ≤ P
P

◦ Le problème SACADOSVECTEUR est le même problème que SACADOS-1, sauf que les (xi )i∈[1..N ]
et Γ sont des vecteurs.

• Montrez que SACADOS-1 et SACADOS-2 sont P-équivalents, que SACADOS-3 et SACADOS-4 sont
P-équivalents, et que SACADOS-4 est une extension de SACADOS-1.
V W
Soit F une formule en forme normale F = 1≤k≤M Ck , avec Ck = 1≤h≤Nk Lk,h où les Lk,h sont des
litteraux sur les variables (vr )1≤r≤S . On envisagera que F soit dans 3SAT, i.e. que les Nk valent tous 3.
On construit des vecteurs à S +M coordonnées. Pour chaque variable vi , on construit les vecteurs xvrai i =
vrai vrai f aux f aux f aux
(0, 0, ..., 0, 1, 0, ..0, xi,1 , ...xi,M ) et xi = (0, 0, ..., 0, 1, 0, ..0, xi,1 , ...xi,M ), les S premières coordonnées
f aux
sont des 0, sauf la ieme qui est un 1. xvrai
i,j vaut 1 si vi est un littéral de la clause Cj , vaut 0 sinon. xi,j
vaut 1 si non(vi ) est un littéral de la clause Cj , vaut 0 sinon. On note X = (xvrai
i )1≤i≤S ∪ (xfi aux )1≤i≤S .

• Montrez que la formule est satisafiable ssi il existe un sous ensemble Y de X et des nombres c1 , ..., cM
P
non nuls tels que Y y = (1, 1, 1, ..., 1, 1, 1, c1 , c2 , ..., cM ).

• Donnez un vecteur Γ et un ensemble Z tel que le problème SACADOSVECTEUR avec pour entrée
X ∪ Z et Γ a une solution ssi F est satisfiable.

• Montrez que SACADOSVECTEUR est NP-complet

• Montrez que SACADOS-1 est NP-complet

• Proposez une heuristique pour SACADOS-3. Montrez que si tous les pi vérifient pi ≤ P/2, alors la
valeur de la solution trouvée est au moins la moitié de la valeur optimale. Adaptez l’heuristique pour
se passer de cette hypothèse.

• Donnez deux algorithmes qui résolvent SACADOS-4 de complexité respectives θ(N ∗ V ) et θ(N ∗ P ).
Pourquoi l’existence de ces algos ne contredit pas la NP-complétude de ces problèmes ?

• Donnez des algos d’approximation de facteur 1 −  pour SACADOS-3. Quelle est leur complexité ?