Master Info - 2015-2016

MIF15 Complexité et Calculabilité


Examen Final

Corrigé rédigé par Paul Brunet et Laure Gonnord
Durée 1H30
Notes de cours et de TD autorisées. Livres et appareils électroniques interdits.
Le barème est donné à titre indicatif .

1 Machines de Turing
Question 1 (4 points)
Construisez une machine de Turing déterministe acceptant le langage L des palindromes
sur {a, b}∗ , défini par L = {w ∈ {a, b}∗ |w = wR , où wR est le mot miroir de w).
Vous écrirez une machine de Turing :
— À un seul ruban infini à droite, le marqueur délimitant le mot d’entrée étant #, la tête
de lecture initialement positionnée sur le premier blanc à gauche de w.
— Qui décide L (avec donc un état d’acceptation et un état de refus).
Votre machine de Turing viendra avec des EXPLICATIONS et un EXEMPLE. Soi-
gnez le dessin et la rédaction !

Solution:
#/#/ ←

a/a/ →
b/b/ →

#/#/ ←
2 3 #/#/ ←

a/#/ → a/#/ ← b/#/ ←

#/#/ → #/#/ → a/a/ ←
0 1 4 NON OUI
b/b/ ←
b/#/ → b/#/ ← a/#/ ←

2’ 3’ #/#/ ←
#/#/ ←

a/a/ →
b/b/ →

MIF15 Complexité et Calculabilité, Master Info - 2015-2016 1/7

2 Fonctions primitives récursives

Définition. Une fonction f : Nn → N (avec n ≥ 0) est récursive primitive si elle est :

— Une des fonctions renvoyant 0 : zeron : (x1 . . . xn ) 7→ 0. La fonction constante zero0 : () 7→ 0
sera par abus de notation souvent notée 0.
— succ : x 7→ x + 1 la fonction successeur (alors n = 1) ;
— idin : (x1 , . . . , xn ) 7→ xi les fonctions de projection, pour 1 ≤ i ≤ n ;
et stable par les opérations de base :
— Compn (g, h1 , . . . , hm ) : (x1 , . . . , xn ) 7→ g(h1 (x1 , . . . , xn ), . . . , hm (x1 , . . . , xn )) la composi-
tion. Notons que n désigne ici l’arité de la fonction obtenue (le nombre d’arguments, qui
peut être 0), et m désigne l’arité de la fonction g. Le cas m = 0 permet de construire des
fonctions avec g d’arité 0.
— Rec(g, h) la fonction définie par récurrence (à droite) comme
(
f (x1 , . . . , xn−1 , 0) = g(x1 , . . . , xn−1 ),
f (x1 , . . . , xn−1 , m + 1) = h(x1 , . . . , xn−1 , m, f (x1 , . . . , xn−1 , m)),

MIF15 Complexité et Calculabilité, Master Info - 2015-2016 2/7

Question 2 (3 points)
La fonction SommeDiviseurs est définie de la façon suivante : si n ∈ N, alors SommeDiviseurs(n)
renvoie la somme des diviseurs entiers positifs de n (n non compris).
Par exemple SommeDiviseurs(6) = 1 + 2 + 3 = 6.
Montrez que SommeDiviseurs est primitive récursive.
On pourra définir une fonction auxiliaire avec un argument de plus. On pourra également
utiliser la fonction modulo(n, m) 7→ n[m] (ou n mod m) supposée primitive récursive,
et une définition par cas ite(x, y, b) = if (b > 0) then x else y supposée aussi primitive
récursive.

Solution:
On peut définir sommebis(n, i) qui fait la somme des diviseurs de n jusqu’à i. On a assez
facilement :
— sommebis(n, 0) = 0
(
i+1 si modulo(n, i + 1) > 0
— sommebis(n, i + 1) = sommebis(n, i) +
0 sinon
Il resterait à recoller les morceaux.

Question 3 (3 points)
Soit g une fonction récursive primitive.
Soit f la fonction définie par f (0, x) = g(x) et f (n + 1, x) = f (n, f (n, x)).
Montrez que f est récursive primitive.
n
On commencera par prouver proprement que f : (n, x) 7→ g 2 (x), et on pourra utiliser sans
preuve le fait que la fonction 2 puis : n 7→ 2n , est récursive primitive.

Solution:
La première chose à faire est de prouver une spécification alternative de f :
n
∀n ∈ N, f (n, x) = g 2 (x).

Ce résultat se prouve aisément par récurrence :

0
— f (0, x) = g(x) = g 2 (x) ;
— f (n + 1, x) = f (n, f (n, x)) en appliquant deux fois l’hypothèse de récurrence, on
n n n+1
obtient f (n + 1, x) = g 2 (g 2 (x)) = g 2 (x).
On va donc commencer par définir par récurrence une fonction h telle que h(x, n) = g n (x).
— h(x, 0) = x = id11 (x) ;
— h(x, n + 1) = g(h(x, n)) = Comp3 (g, id33 )(x, n, h(x, n)).
Donc on peut définir h par :

h := Rec(id11 , Comp3 (g, id33 )).

Avec h et 2 puis on peut finalement écrire f (n, x) = h(x, 2 puis(n)), soit :

f := Comp2 (Rec(id11 , Comp3 (g, id33 )), id22 , Comp2 (2 puis, id12 ))

MIF15 Complexité et Calculabilité, Master Info - 2015-2016 3/7

3 Indécidabilité
Question 4 (2 points)
Montrez, par réduction à partir du problème de l’arrêt, que le problème suivant est indécidable :
entrée : une machine de Turing M qui s’arrête sur toutes les données.
question : L(M ) est-il infini ?

Solution:
Soit < M, w > une instance du problème de l’arrêt. On construit M0 comme suit :
— M0 prend en entrée un compteur c.
— Si M s’arrête en moins de c étapes, M0 accepte, sinon elle rejette.
M0 accepte c ssi M s’arrête en moins de c étapes sur w. L(M0 ) = {c ∈ Ntels que c ≥
longueur du calcul de M sur w} est donc infini ssi M s’arrête sur w.

4 Problème : NP-complétude

Le problème Clique consiste à établir si un graphe G donné contient une clique de cardinal
égal à un entier donné k. Un graphe G est défini par la donnée de son ensemble de sommets V
et de l’ensemble de ses arêtes E ⊆ V × V . Le cardinal d’un graphe est son nombre de sommets.
Un ensemble C ⊆ V de sommets de G est une clique si tous ces sommets sont reliés entre eux
dans G, c’est à dire :
∀u, v ∈ C, u 6= v ⇒ (u, v) ∈ E.

Question 5 (1 point)
Donnez un exemple de graphe contenant une clique de cardinal quatre.

Solution:
On pose G = (V, E) avec V = {0, 1, 2, 3} et E = V × V . Il est trivial de vérifier que V
lui-même est une clique de cardinal quatre dans G.

0 1

2 3

MIF15 Complexité et Calculabilité, Master Info - 2015-2016 4/7

Le problème Clique s’énonce de la manière suivante :
Clique :
entrée : un graphe G = (V, E) et un entier k
question : existe-t-il une clique C dans G de cardinal égal à k ?
Nous allons monter que ce problème est NP-complet, en le réduisant depuis Sat. Pour cela nous
allons suivre une preuve proposée par Richard Karp en 1972.
Soit F une formule en forme normale conjonctive. On définit le graphe GF = (VF , EF ) comme
suit :
— les sommets de ce graphe sont les paires (`, c), où c est une clause de F et ` est un littéral
(c’est à dire une variable ou sa négation) qui apparaı̂t dans c ;
— les sommets (`, c) et (`0 , c0 ) sont reliés dans le graphe si et seulement si c 6= c0 et ` n’est pas
la négation de `0 .
Par exemple si F = c1 ∧ c2 ∧ c3 avec c1 = (x ∨ y), c2 = (¬x ∨ ¬y) et c3 = (¬x ∨ y), GF est le
graphe suivant :

x, c1 y, c1

¬x, c2 y, c3

¬y, c2 ¬x, c3

Question 6 (3 points)
Montrez que si F est constituée de n clauses, alors F est satisfiable si et seulement si
GF contient une clique de cardinal n. On prouvera soigneusement les deux implications en
construisant une clique dans un sens, et une interprétation des formules dans un autre.

Solution:
Si F est satisfiable, soit I un modèle de F . Pour chaque clause ck de F , il y a au moins un
littéral `(ck ) dans ck tel que [`(ck )]I = 1. Considérons un tel ensemble CI = {(`(ck ), ck )}.
F a n clauses, donc le cardinal de CI vaut n. De plus, si (`, c) et (`0 , c0 ) sont deux éléments
différents de CI , alors c 6= c0 et comme [`]I = [`0 ]I = 1, ` et `0 ne sont pas la négation l’un
de l’autre. Donc ((`, c), (`0 , c0 )) ∈ EF . CI est donc une clique de cardinal n dans GF .
Supposons au contraire qu’on a une clique C ⊆ VF de cardinal n. On peut définir une
interprétation IC de la manière suivante :

1 si (p, c) ∈ C, pour une certaine clause c

IC (p) = 0 si (¬p, c) ∈ C, pour une certaine clause c

0 sinon


Comme C est une clique, pour tous (`, c) et (`0 , c0 ) différents dans C ces deux sommets
sont reliés dans GF , ce qui implique en particulier que c et c0 sont des clauses différentes.
Comme de plus le cardinal de C est égal au nombre de clauses de F , on en déduit que
pour chaque clause c de F il y a un littéral ` tel que (`, c) ∈ C. Par définition de IC , on a
[`]IC = 1. Par conséquent comme IC valide au moins un littéral dans chaque clause de F ,
[F ]IC = 1, ce qui signifie que F est satisfiable.

Question 7 (2 points)

MIF15 Complexité et Calculabilité, Master Info - 2015-2016 5/7

 On définit la taille |F | d’une formule F par le nombre de littéraux qui la constituent (dans
l’exemple ci-dessus, |F | = 6), et la taille |G| d’un graphe comme la somme de son cardinal
(nombre de sommets) et de son nombre d’arêtes.
Bornez |GF | par un polynôme en |F |
(c’est-à-dire trouvez un polynôme p tel que |GF | 6 p(|F |)).
Solution:
D’après la définition de GF , on voit que chaque littéral de F donne lieu à au plus un
sommet dans VF . On en déduit que le cardinal de VF est inférieur à |F |. De plus, le
nombre d’arêtes étant borné par le carré du nombre de sommets, on a :

|GF | = |VF | + |EF | 6 |VF | + |VF |2 6 |F | + |F |2 .

Question 8 (2 points)
En utilisant les résultats précédents, prouvez que Clique est NP-complet.
Solution:
On commence par montrer que Clique est NP-dur. Pour cela on donne une réduction
polynomiale depuis Sat. Soit ρ la fonction qui à une formule F en forme normale conjonc-
tive associe (GF , n), avec n le nombre de clauses de F . D’après la question 7, on sait que
GF est de taille polynomiale par rapport à la taille de F , et il est évident à partir de la
définition de GF que la construction de ce graphe est linéaire en sa taille. Le calcul de n
ne pose pas plus de problème. Donc ρ est une fonction P. D’après la question 6, on sait
que :
F ∈ Sat ⇔ ρ(F ) = (GF , n) ∈ Clique.
Par conséquent, ρ est bien une réduction polynomiale de Sat à Clique, et comme Sat
est NP-complet, Clique est NP-dur.
Il faut encore montrer que Clique appartient bien à la classe NP. Considérons l’algorithme
non déterministe suivant :
input : Un graphe G = (V, E) et un entier n
output: Un booléen, indiquant si G possède une clique de taille n.
N ← 0;
C ← ∅;
pour v ∈ V faire
choix entre
C ← C ∪ {v};
N ← N + 1;
ou
ne rien faire ;
finchoix
finpour
si N = n alors
pour u, v ∈ C faire
si u 6= v et (u, v) ∈
/ E alors
retourner (faux);
finsi
finpour
retourner (vrai) ;
sinon
retourner (faux);
finsi
MIF15 Complexité et Calculabilité, Master Info - 2015-2016 6/7
 Cet algorithme calcule de manière non-déterministe (“devine”) une clique , puis vérifie
que c’est bien une clique de taille n. Il s’exécute en temps polynomial par rapport à |G|.
Par conséquent on a établi que Clique est bien dans la classe NP.

MIF15 Complexité et Calculabilité, Master Info - 2015-2016 7/7