Problème de correspondance de Post

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Théorème PCP.

En mathématiques, et plus précisément en théorie de la calculabilité, le problème de correspondance de Post est un problème de décision indécidable qui fut introduit par Emil Post en 1946[1]. Comme il est plus simple que le problème de l'arrêt et que le problème de la décision, il apparaît souvent dans des démonstrations d'indécidabilité.

Définition du problème[modifier | modifier le code]

Les données du problème sont deux listes finies \alpha_{1}, \ldots, \alpha_{N} et \beta_{1}, \ldots, \beta_{N} de mots d'un alphabet A ayant au moins deux symboles. Une solution du problème est une suite d'indices (i_k)_{1 \le k \le K} avec K \ge 1 et  1 \le i_k \le N pour tous les k, telle que les concaténations \alpha_{i_1} \ldots \alpha_{i_K} et \beta_{i_1} \ldots \beta_{i_K} soient égales.

Le problème de correspondance de Post (PCP) consiste à déterminer si une solution existe ou non.

Exemples[modifier | modifier le code]

Exemple 1[modifier | modifier le code]

Soit les deux listes suivantes :

α1 α2 α3
a ab bba
β1 β2 β3
baa aa bb

Une solution à ce problème est la suite (3, 2, 3, 1), parce que

\alpha_3 \alpha_2 \alpha_3 \alpha_1 = bba + ab + bba + a = bbaabbbaa = bb + aa + bb + baa = \beta_{3} \beta_{2} \beta_{3} \beta_{1}.

De plus, toutes les « répétitions » de cette solution, comme (3, 2, 3, 1, 3, 2, 3, 1), etc. sont également des solutions ; lorsqu'une solution existe, il y en a toujours une infinité de ce type.

En revanche, si les deux listes avaient été \alpha_2, \alpha_3 et \beta_{2}, \beta_{3}, il n'y aurait aucune solution, parce qu'alors aucune paire se correspondant n'a la même dernière lettre, ce qui doit obligatoirement apparaître à la fin d'une solution.

On peut voir une instance du problème de Post comme une collection de blocs de la forme

αi
βi

(chaque type de bloc étant fourni en nombre illimité). Ainsi, l'exemple précédent correspond aux trois types de blocs

a
baa
ab
aa
bba
bb
i = 1 i = 2 i = 3

(fournis en quantité illimitée). Une solution correspond à un arrangement de blocs côte à côte tel que la chaîne de caractères du haut est identique à celle du bas. Ainsi, la solution donnée précédemment correspond à :

bba
bb
ab
aa
bba
bb
a
baa
i1 = 3 i2 = 2 i3 = 3 i4 = 1

Exemple 2[modifier | modifier le code]

Utilisant cette représentation par des blocs, l'exemple suivant admet une infinité de solutions non répétitives.

bb
b
ab
ba
c
bc
1 2 3

Dans ce cas, toutes les séquences de la forme (1, 2, 2, . . ., 2, 3) sont des solutions :

bb
b
ab
ba
ab
ba
ab
ba
c
bc
1 2 2 2 3

Esquisse de démonstration de l'indécidabilité[modifier | modifier le code]

La démonstration la plus fréquente de l'indécidabilité du problème de Post consiste à construire une instance du problème qui simule le calcul d'une machine de Turing sur une entrée particulière, une solution correspondant à l'acceptation de l'entrée par la machine. Comme décider si une machine de Turing accepte une entrée donnée est indécidable, le problème de Post l'est aussi. L'analyse qui suit est basée sur le manuel de Michael Sipser, Introduction to the Theory of Computation[2].

L'idée est de faire coder l'historique du calcul (en) de la machine de Turing par la chaîne de caractères à faire correspondre en haut et en bas des blocs, cette chaîne commençant par des caractères décrivant l'état initial, puis l'état suivant, etc. (ces états étant séparés par un caractère spécial, noté ici #). Par définition d'une machine de Turing, un état est formé de trois données :

  • L'état de la machine proprement dite, c'est-à-dire le contenu du registre d'état.
  • Le contenu actuel du ruban.
  • La position actuelle de la tête de lecture/écriture.

Le codage d'un état est la liste des symboles écrits sur le ruban, plus un symbole spécial pris parmi les q1 à qk, représentant chacun des k états possibles du registre, ce symbole étant écrit à la position correspondant à celle de la tête de lecture/écriture sur le ruban. Ainsi, pour l'alphabet {0,1}, un état typique pourra être codé par : 101101110q700110, et un historique de calcul par : q0101#1q401#11q21#1q810.

Les blocs correspondants sont construits de telle sorte que les seuls assemblages possibles simulent le fonctionnement de la machine. Le premier bloc est ainsi

 
q0x#

x est l'état initial du ruban et q0 l'état de départ du registre. À partir de ce point, la ligne du haut est toujours en retard d'un état sur celle du bas, et ne la rattrape qu'en atteignant l'état final.

Pour chaque symbole a de l'alphabet du ruban (et pour #), un bloc de copie le transfère d'un état au suivant :

a
a

Pour chaque transition possible, un bloc simule le déplacement de la tête, le changement du registre d'état, et le nouveau caractère écrit. Dans l'exemple suivant, la machine est dans l'état 4, la tête de lecture/écriture, située sur un 0, le change en 1 et se déplace vers la droite, puis le registre passe dans l'état 7 :

q40
1q7

Enfin, lorsque la ligne du bas atteint un état final (correspondant à l'acceptation de l'entrée par la machine), les blocs suivants ont pour fonction de faire « disparaitre » les symboles voisins de la tête de lecture/écriture de la ligne du bas, permettant à celle du haut de la rattraper : si qf est un état final, et a un symbole du ruban, cela correspond aux blocs :

qfa
qf
et
aqf
qf
, suivis d'un dernier bloc
qf
 

Certains détails n'ont pas été mentionnés (comme la gestion des frontières entre états, ou la garantie que le bloc initial est effectivement le premier utilisé), mais cette description montre en gros comment un puzzle statique peut simuler le fonctionnement dynamique d'une machine de Turing.

Variantes[modifier | modifier le code]

De nombreuses variantes du PCP ont été envisagées ; cela vient entre autres de ce que, lorsqu'on essaie de démontrer l'indécidabilité d'un problème en le ramenant au PCP, on n'arrive souvent qu'à le réduire à une version apparemment plus faible de ce problème.

  • Si on fixe n, le nombre de types de blocs utilisables, le problème devient décidable pour n ≤ 2, et reste indécidable pour n ≥ 7. Le statut du problème est inconnu pour 3 ≤ n ≤ 6.
  • Le problème de correspondance de Post circulaire pose la même question pour des indices i_1, i_2,\ldots tels que les mots \alpha_{i_1} \cdots \alpha_{i_k} et \beta_{i_1} \cdots \beta_{i_k} sont conjugués, c'est-à-dire égaux à une rotation des indices près. Cette variante est également indécidable[3].
  • Une des plus importantes variantes du PCP est le problème de correspondance de Post borné, consistant à déterminer s'il existe un couple de mots correspondants n'utilisant que k blocs (se répétant ou non). Une recherche par force brute résout le problème en un temps O(2k)[4], mais, le problème étant NP-complet, cette borne semble difficilement améliorable[5]. Contrairement à d'autres problèmes NP-complets tels que le problème SAT, le problème de correspondance borné reste difficile même en moyenne sur des entrées choisies au hasard[6].
  • Une autre variante est le problème de correspondance de Post marqué, pour lequel chaque ui et chaque vi doivent commencer avec des symboles distincts. Halava, Hirvensalo, et de Wolf ont montré que cette variante est décidable en temps exponentiel. Ils montrèrent de plus qu'un léger affaiblissement de cette contrainte (en exigeant seulement que les deux premiers caractères diffèrent) rend à nouveau le problème indécidable[7].
  • Le problème de plongement de Post demande à ce que le mot \alpha_{i_1} \cdots \alpha_{i_k} soit une sous-chaîne (non nécessairement d'un seul tenant) de la chaîne \beta_{i_1} \cdots \beta_{i_k}. Sous cette forme, il est évidemment décidable, et ce en temps très rapide, mais si l'on exige de plus que les solutions appartiennent à un langage régulier donné (obtenant le problème de plongement régulier de Post), sa complexité augmente énormément, dominant toutes les fonctions récursives primitives[8].
  • Le problème de correspondance avec l'identité consiste à déterminer si un ensemble fini de paires de mots (sur un alphabet formé de lettres et de leurs inverses, autrement dit d'éléments du groupe libre à n générateurs) peut engendrer la paire identité par concaténations, autrement dit si le monoïde engendré par un ensemble fini de couples de mots est un groupe ; ce problème est indécidable[9].

Références[modifier | modifier le code]

  1. (en) E. L. Post, « A variant of a recursively unsolvable problem », Bull. Amer. Math. Soc, vol. 52,‎ 1946 (lire en ligne)
  2. (en) Michael Sipser, Introduction to the Theory of Computation, Thomson Course Technology,‎ 2005, 199–205 p. (ISBN 0-534-95097-3), « A Simple Undecidable Problem »
  3. (en) K. Ruohonen, « On some variants of Post's correspondence problem », Acta Informatica, Springer, vol. 19, no 4,‎ 1983, p. 357–367 (DOI 10.1007/BF00290732)
  4. Voir pour cette notation l'article Comparaison asymptotique
  5. (en) Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman,‎ 1979 (ISBN 0-7167-1045-5), p. 228
  6. (en) Y. Gurevich, « Average case completeness », J. Comp. Sys. Sci., Elsevier Science, vol. 42, no 3,‎ 1991, p. 346–398 (DOI 10.1016/0022-0000(91)90007-R)
  7. (en) V. Halava, « Marked PCP is decidable », Theor. Comp. Sci., Elsevier Science, vol. 255,‎ 2001, p. 193–204 (DOI 10.1016/S0304-3975(99)00163-2)
  8. (en) P. Chambart, « Post embedding problem is not primitive recursive, with applications to channel systems », Lecture Notes in Computer Science, Springer, vol. 4855,‎ 2007, p. 265–276 (ISBN 978-3-540-77049-7, DOI 10.1007/978-3-540-77050-3_22)
  9. (en) Paul C. Bell, « On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups », International Journal of Foundations of Computer Science, World Scientific, vol. 21.6,‎ 2010, p. 963-978 (DOI 10.1142/S0129054110007660)

Liens externes[modifier | modifier le code]