Cours d’algorithmique du 14 décembre 1999 Natacha Portier

Le théorème de Stockmeyer et Meyer (1973)

Définition 1 Une expression rationnelle arithmétique E et le sous-ensemble L(E) de N qu’elle représente sont définis de la manière récursive suivante :

– Les expressions 0 et 1 sont des ERA(expressions rationnelles arithmétiques) et représentent respectivement L(0) = {0} et L(1) = {1}.

– Si E_{1} et E_{2} sont des ERA alors (E_{1} ∪ E_{2}) est une ERA et L(E_{1} ∪ E_{2}) = L(E_{1}) ∪ L(E_{2}).

– Si E_{1} et E_{2} sont des ERA alors (E_{1}.E_{2}) est une ERA et L(E_{1}.E_{2}) = L(E_{1}) + L(E_{2}) = {x + y | x ∈ L(E_{1}) et y ∈ L(E_{2})}.

Si E est une ERA, nous noterons : E^{0} = 0, E^{1} = E et pour tout n entier naturel E^{n+1} = E^{n}.E

– Si E est une ERA alors (E^{∗}) est une ERA et L(E^{∗}) = ⋃_{n≥0} L(E^{n}).

Exemples :

– L(0^{∗}) = {0}

– L(1^{∗}) = N

– L(1^{n}) = {n}

– (1^{2})^{∗} représente les entiers pairs.

– (1^{2})^{∗}.1 représente les entiers impairs.

Remarques :

– Nous prendrons des libertés avec les parenthésages des ERA quand il n’y a pas d’ambiguïté.

– Une ERA est une expression formelle, un mot sur un certain alphabet. Deux ERA sont égales si et seulement si elles s’écrivent exactement pareil.

– Deux ERA différentes peuvent représenter le même ensemble, par exemple 1^{∗}, (1^{2})^{∗} ∪ 1.(1^{2})^{∗} et 0 ∪ 1.1^{∗} représentent N.

De même E^{∗} et (E^{∗})^{∗} représentent le même ensemble.

– Propriété (admise) : Les ensembles représentés par les ERA sont exactement les unions finies de progressions arithmétiques.

Nous pouvons maintenant énoncer le théorème de Stockmeyer et Meyer (1973) :

Théorème 1 Savoir si une ERA ne représente pas N tout entier est un problème NP-complet.

Remarque : la taille de l’ERA est mesurée par le nombre de symboles 0 et 1 qui interviennent dans son écriture.

Nous allons commencer par montrer que le problème est NP-dur. Puis nous montrerons des lemmes qui nous permettrons de prouver que le problème est NP, ce qui achèvera la preuve de la NP-complétude.

Nous réduisons 3-SAT à ce problème pour montrer qu’il est NP-dur. Une formule 3SAT est de la forme ∧_{k=1}^{m}C_{k} où C_{k} = (v_{k,1} ∨ v_{k,2} ∨ v_{k,3}) avec v_{k,i} ∈ X = {x_{1}, ¬x_{1}, x_{2}, ¬x_{2}, x …, x_{n}, ¬x_{n}, x}.

Soient p_{1}, ..., p_{n} les n premiers nombres premiers (nous pouvons les obtenir par exemple grâce à un crible d’Eratosthène sur les entiers entre 1 et n^{2} pour n suffisemment grand). Considérons le système :

\{ \begin{matrix}z ≡ z_{1} [p_{1}] \\ … \\ z ≡ z_{n} [p_{n}] \end{matrix}

Nous dirons que z est un code de (z_{1}, …, z_{n}) s’il satisfait ce système. D’après le théorème des restes chinois il a une solution. De plus, il existe une solution t comprise entre 0 et Πp_{i} − 1 et l’ensemble des solutions positives est l’ensemble des termes de la suite arithmétique de premier terme t et de raison Πp_{i}. Nous allons construire une ERA qui représente l’ensemble des entiers qui ne codent pas une solution de notre formule 3SAT fixée. Il peut y avoir deux raisons pour lesquelles (z_{1}, …, z_{n}) ne satisfait pas la formule. La première est qu’un des z_{i} ne soit pas un booléen, la deuxième est qu’une des clauses ne soit pas satisafaite.

L’entier z ne code pas un booléen si pour un certain i compris entre 1 et n, l’entier z_{i} n’est pas booléen, i.e. est compris entre 2 et p_{i} − 1. Donc z ne code pas un booléen s’il appartient au sous-ensemble représenté par :

E_{0} = ⋃_{1≤i≤n, 2≤k≤p_{i}} 1^{k}.(1^{p_{i}})^{∗}

Si z n’est pas le code d’un uple qui satisfasse la formule alors il existe k compris entre 1 et m tel que (z_{1}, …, z_{n}) ne satisfasse pas C_{k}. Cela signifie que :

\{ \begin{matrix}z ≡ z_{i_{1}} [p_{i_{1}}] \\ z ≡ z_{i_{2}} [p_{i_{2}}] \\ z ≡ z_{i_{3}} [p_{i_{3}}] \end{matrix}

avec C_{k} = (v_{k,1} ∨ v_{k,2} ∨ v_{k,3}), z_{i_{1}} = 0 si v_{k,1} = x_{i_{1}} et z_{i_{1}} = 1 si v_{k,1} = ¬x_{i_{1}}, z_{i_{2}} = 0 si v_{k,2} = x_{i_{2}} et z_{i_{2}} = 1 si v_{k,2} = ¬x_{i_{2}}, z_{i_{3}} = 0 si v_{k,3} = x_{i_{3}} et z_{i_{3}} = 1 si v_{k,3} = ¬x_{i_{3}}. Soit t_{k} un entier compris entre 0 et p_{i_{1}}p_{i_{2}}p_{i_{3}} qui satisfasse ce système. Alors z n’est pas le code d’un uple qui satisfasse C_{k} s’il appartient au sous-ensemble représenté par :

E_{k} = 1^{t_{i}}.(1^{p_{i_{1}}p_{i_{2}}p_{i_{3}}})^{∗}

Donc finalement z ne code pas une solution de la formule si et seulement s’il appartient au sous-ensemble représenté par l’expression ⋃_{1≤k≤m} E_{k} ∪ E_{0}.

□

Montrons maintenant que le problème est NP. Pour cela, nous commençons par montrer un théorème.

Théorème 2 Soit G un graphe orienté et S_{d} et S_{f} deux sommets différents de G. Existe t’il un entier n tel qu’il n’y ait pas de chemin orienté de longueur n de S_{d} à S_{f}? Ce problème est NP.

Pour montrer ce théorème nous utilisons trois lemmes. Le lemme suivant fait le lien entre ERA et graphes orientés et nous permet de montrer que le problème est NP :

Lemme 1 Soit E une ERA de taille N. Il existe un graphe orienté G de taille au plus 3N − 1 et deux sommets S_{d} et S_{f} tels que pour tout entier strictement positif n, il existe un chemin de longueur n de S_{d} à S_{f} si et seulement si n appartient à L(E).

La preuve se fait par induction sur l’ensemble des ERA. Pour chaque expression E de taille N nous construisons (G, S_{d}, S_{f}, e) où G est un graphe orienté de taille au plus 4N − 2, S_{d} et S_{f} sont deux sommets du graphe, e est égal à 0 si 0 appartient à L(E) et 1 sinon et pour tout entier strictement positif n il existe un chemin de longueur n de S_{d} à S_{f} si et seulement si n appartient à L(E).

– Pour l’expression 0 le graphe a deux sommets S_{d} et S_{f}, aucune arête et e est égal à 0.

Pour l’expression 1 le graphe a deux sommets S_{d} et S_{f}, une arête de S_{d} à S_{f} et e est égal à 1.

Soient E′ et E′′ des ERA et supposons avoir construit (G′, S′_{d}, S′_{f}, e′) et (G′′, S′′_{d}, S′′_{f}, e′′). Nous construisons alors (G, S_{d}, S_{f}, e) pour l’expression E de la manière suivante.

– Si E = E′^{∗} alors le graphe G est le graphe G′ auquel nous ajoutons des arêtes. Les sommets S_{d} et S_{f} sont égaux à S′_{d} et S′_{f}. Si dans G′ il existe une arête d’un sommet S à S′_{f} alors dans G il y a une arête de S à S_{d}. Pour finir e = 0.

– Soit E = E′.E′′. Le graphe G est l’union du graphe G′ et du graphe G′′ à laquelle nous ajoutons des arêtes. Les sommets S_{d} et S_{f} sont égaux à S′_{d} et S′′_{f}. S’il y a dans G′ une arête entre un sommet S′ et S′_{f} alors nous ajoutons dans G une arête entre S′ et S′′_{d}. Si e′ = 0 et s’il y a dans G′′ une arête entre un S′′_{d} et un sommet S′′ alors nous ajoutons dans G une arête entre S_{d} et S′′. Si e′′ = 0 et s’il y a dans G′ une arête entre un sommet S′ et S′_{f} alors nous ajoutons dans G une arête entre S′ et S_{f}. Enfin, e est nul si et seulement si e′ et e′′ sont nuls.

– Soit E = E′ ∪ E′′. Le graphe G est l’union des graphes G′ et G′′ à laquelle nous ajoutons un nouveau sommet S_{f} ainsi que de nouvelles arêtes. Le sommet S_{d} est égal à S′_{d}. Si dans G′′ il y a une arête entre S′′_{d} et un sommet S′′ alors nous ajoutons dans G une arête entre S_{d} et S′′. Si dans G′′ il y a une arête entre S′′_{d} et S′′_{f} alors dans G il y a une arête entre S_{d} etS_{f}. Si dans G′ ou G′′ il y a une arête entre un sommet S et S′_{f} ou S′′_{f} alors dans G il y a une arête entre S et S_{f}. Enfin, e est nul si et seulement si e′ ou e′′ est nul.

□

Lemme 2 Soit G un graphe orienté avec N sommets et S_{d} et S_{f} deux sommets différents de G. Soit n_{0} un entier tel qu’il n’existe pas de chemin orienté de longueur n_{0} de S_{d} à S_{f}. Alors il existe un entier n_{1} strictement inférieur à 2^{N} tel qu’il n’existe pas de chemin orienté de longueur n_{1} de S_{d} à S_{f}.

Démonstration : Soit T_{n}(S_{d}) l’ensemble des sommets S de G tels qu’il existe un chemin de longueur n de S_{d} à S. Si T_{n}(S_{d}) = T_{m}(S_{d}) alors nous avons T_{n+1}(S_{d}) = T_{m+1}(S_{d}) et donc pour tout k entier naturel T_{n+k}(S_{d}) = T_{m+k}(S_{d}). Or il y a 2^{N} sous-ensembles possibles des sommets de G. Donc S_{f} n’appartient pas à un des T_{n}(S_{d}) si et seulement s’il existe n_{0} < 2^{N} tel que S_{f} n’appartienne pas à T_{n_{0}}(S_{d}).

□

Lemme 3 Soit G un graphe orienté avec N sommets et S_{d} et S_{f} deux sommets différents de G. Soit n un entier naturel écrit en base 2 : n = ϵ_{0} + 2ϵ_{1} + ⋯ + 2^{p}ϵ_{p}. Alors il existe un algorithme qui décide s’il existe un chemin de longueur n dans le graphe de S_{d} à S_{f} en temps polynomial en N et p = ⌊log_{2} n⌋.

Démonstration : Pour tout sommet s du graphe et pour tout entier naturel m on définit T_{m}(s) comme l’ensemble des sommets du graphe accessible à partir de s par un chemin de longueur m.

On a la propriété :

T_{m+l}(s) = ⋃_{x∈T_{m}(s)} T_{l}(x) = ⋃_{x∈T_{l}(s)} T_{m}(x)

Donc

T_{n}(S_{d}) = ⋃_{x_{0}∈T_{ϵ_{0}}(S_{d})} T_{2ϵ_{1}+···+2^{p}ϵ_{p}}(x_{0})

et

T_{n}(S_{d}) = ⋃_{x_{0}∈T_{ϵ_{0}}(S_{d})} ⋃_{x_{1}∈T_{2ϵ_{1}}(x_{0})} ⋯ ⋃_{x_{p−1}∈T_{2^{p−1}ϵ_{p−1}}(x_{p−2})} T_{ϵ_{p}2^{p}}(x_{p−1})

L’algorithme cherché est le suivant. Nous calculons récursivement T_{1}(s) pour tous les sommets s, puis T_{2}(s) pour tous les sommets s, T_{4}(s) pour tous les sommets s et ainsi de suite jusqu’à T_{2^{p}}(s). Nous en déduisons T_{n}(S_{d}) grâce à la formule précédente. Remarquons que tous les T_{m}(s) sont de cardinal au plus N.

□

Nous pouvons maintenant montrer le Théorème 1.

Soit E une ERA de taille N. Nous construisons (et il est clair que l’algorithme est polynomial) un graphe orienté G de taille au plus 3N − 1 tel que pour tout entier strictement positif n, il existe un chemin du sommet S_{d} au sommet S_{f} dans G si et seulement si n appartient à L(E). Il est facile de vérifier si 0 appartient ou non à L(E). S’il existe n non nul n’appartenant pas à L(E), alors il existe n inférieur à 2^{3N−1} tel qu’il n’y ait pas de chemin de longueur n entre S_{d} et S_{f}. Si l’entier n est donné par son écriture en base 2 alors nous pouvons le vérifier en temps polynomial, ce qui prouve que le problème est NP.

□

Références

[1] Stockmeyer, L. J. and Meyer, A. R., Word problems requiring exponential time: preliminary report. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), pp. 1–9, Assoc. Comput. Mach., New York, (1973)