On the Complexity of the Bi-infinite Post Correspondence Problem

Cet article établit que le problème de correspondance de Post bi-infini ($\mathbb{Z}$PCP) est $\Sigma^0_2$-complet au sein de la hiérarchie arithmétique en présentant une chaîne de réductions à partir de la non-halting de la machine de Turing et en prouvant la $\Pi^0_1$-complétude de plusieurs variantes infinies et décalées connexes.

L'essentiel

Imaginez que vous jouez à un jeu avec deux enregistreurs de bandes infinies, l'Enregistreur G et l'Enregistreur H. Vous avez un jeu de cartes, et chaque carte possède deux faces : une « face G » et une « face H ». Chaque face contient une chaîne de lettres (comme « pomme » ou « banane »).

Le jeu est simple : vous devez choisir une séquence de cartes et les empiler.

• Si vous lisez les faces G du haut vers le bas, vous obtenez une longue chaîne de lettres.
• Si vous lisez les faces H du haut vers le bas, vous obtenez une autre longue chaîne de lettres.

L'objectif est de trouver une séquence de cartes où la chaîne G et la chaîne H sont exactement les mêmes. C'est le célèbre Problème de la Correspondance de Post (PCP). C'est un casse-tête classique qui s'avère impossible à résoudre pour chaque jeu de cartes possible ; il n'existe pas d'algorithme général capable de dire « Oui, une solution existe » ou « Non, c'est impossible » pour tous les cas.

Le Nouveau Twist : Le Jeu « Bi-infini »

Au lieu de commencer au sommet d'une pile et de descendre, imaginez que la pile de cartes s'étend à l'infini dans les deux directions : infiniment vers la gauche et infiniment vers la droite.

• Vous recherchez une séquence de cartes s'étendant de $-\infty$ à $+\infty$.
• La règle est la même : la chaîne G infinie doit correspondre à la chaîne H infinie.

Cependant, il y a un piège. Parce que la chaîne est infinie dans les deux sens, les deux chaînes n'ont pas besoin de commencer exactement au même « point zéro ». Elles peuvent être décalées. Imaginez que la chaîne H est simplement la chaîne G, mais que quelqu'un l'a fait glisser légèrement vers la gauche ou la droite. Si vous pouvez faire glisser l'une pour qu'elle corresponde parfaitement à l'autre, vous avez résolu le puzzle.

La Grande Question : À quel point est-ce difficile ?

Les informaticiens classent les problèmes selon leur degré de « difficulté » en utilisant une échelle appelée Hiérarchie Arithmétique.

• Niveau 1 (Les premiers échelons) : Les problèmes sont « indécidables » mais peuvent être prouvés en trouvant un exemple unique (comme le PCP original).
• Niveau 2 (L'échelon suivant) : Les problèmes sont encore plus difficiles. Pour prouver qu'une solution existe, vous pourriez avoir besoin de vérifier un nombre infini de possibilités d'une manière spécifique.

La Découverte de l'Article :
Les auteurs, Olivier Finkel et Vesa Halava, ont prouvé que le jeu bi-infini (ZPCP) se situe strictement au Niveau 2 de cette échelle.

• Il est plus difficile que le PCP standard (Niveau 1).
• Il n'est pas au sommet absolu de l'univers des problèmes ; il possède une complexité spécifique et gérable.
• Crucialement, ils ont prouvé qu'il ne se trouve pas dans les parties « faciles » du Niveau 1. Il nécessite un type de logique plus complexe pour déterminer si une solution existe.

Comment l'ont-ils prouvé ? (L'analogie de la Machine à Remonter le Temps)

Pour prouver cela, les auteurs ont construit un pont entre ce jeu de cartes et le comportement d'une Machine de Turing (un ordinateur théorique capable de simuler n'importe quel algorithme).

1. La Machine à Remonter le Temps : Imaginez une Machine de Turing comme un robot lisant une bande. Si le robot tourne éternelnement sans s'arrêter, il est « non-terminaisons ». S'il s'arrête, il « s'arrête » (halt).
2. La Traduction : Les auteurs ont créé un ensemble de règles spéciales (un « système de semi-Thue ») qui agit comme un traducteur. Ils ont montré que :
   • Si le robot tourne éternellement, vous pouvez construire une pile de cartes infinie qui résout le jeu bi-infini.
   • Si le robot s'arrête, vous ne pouvez pas construire une telle pile.
3. L'astuce de la « Réversibilité » : La clé de leur preuve était de rendre le traducteur « réversible ». Imaginez un film projeté à l'envers. Si vous pouvez rembobiner le film parfaitement jusqu'au début, le système est réversible.
   • Ils ont prouvé que pour leur jeu de cartes spécifique, si vous trouvez une solution, vous pouvez « rembobiner » les étapes jusqu'au tout début du fonctionnement de la Machine de Turing.
   • Si la machine s'était arrêtée (halté), le « rembobinage » heurterait un mur (un état où aucun mouvement précédent n'est possible).
   • Cette capacité de « rembobinage » a forcé le problème dans ce niveau de complexité spécifique du Niveau 2.

Autres Résultats

En cours de route, ils ont résolu quelques sous-puzzles :

• Morphismes Injectifs : Ils ont prouvé que même si vous restreignez le jeu de sorte que chaque carte soit unique et qu'aucune paire de cartes ne produise le même motif de lettres (rendant le jeu « injectif »), le problème reste insoluble et tout aussi difficile.
• Décalages Fixes : Ils ont examiné des versions où le décalage entre les deux chaînes est fixé à un nombre spécifique (par exemple, « La chaîne H est toujours exactement 5 lettres à droite de la chaîne G »). Ils ont prouvé que ces versions sont également incroyablement difficiles (complètes pour le Niveau 1).

L'Essentiel

Cet article est une carte du « paysage de difficulté » des puzzles de mots infinis.

• Le PCP standard est un monstre de « Niveau 1 ».
• Le PCP bi-infini (ZPCP) est un monstre de « Niveau 2 ». Il est strictement plus difficile que l'original, mais pas infiniment plus difficile.
• Les auteurs ont utilisé un mécanisme de « rembobinage » ingénieux (la réversibilité) pour montrer exactement où se situe ce nouveau puzzle sur l'échelle de la difficulté computationnelle.

En bref : Résoudre la version infinie et bidirectionnelle de ce jeu de cartes est un type de « difficulté » spécifique qui est un cran au-dessus de la version originale insoluble, et les auteurs ont précisément localisé où elle se trouve dans l'univers mathématique.

Résumé technique

Résumé technique : Sur la complexité du problème de correspondance de Post bi-infini

Définition du problème
L'article étudie la complexité computationnelle du problème de correspondance de Post bi-infini (ZPCP). Alors que le problème de correspondance de Post (PCP) classique cherche un mot fini non vide $w$ tel que $g(w) = h(w)$ pour deux morphismes donnés, et que le $\omega$PCP (PCP infini) cherche un mot infini, le ZPCP cherche à savoir s'il existe un mot bi-infini $\alpha = \dots a_{-1}a_0a_1 \dots$ tel que $g(\alpha) = h(\alpha)$. Crucialement, l'égalité pour les mots bi-infinis est définie à un décalage près : $g(\alpha) = h(\alpha)$ s'il existe un entier $\tau$ tel que la lettre à la position $i$ dans $g(\alpha)$ est égale à la lettre à la position $i+\tau$ dans $h(\alpha)$.

Des travaux antérieurs ont établi que le ZPCP est indécidable et appartient à la classe $\Sigma^0_2$ de la hiérarchie arithmétique, mais sa position n'était pas strictement localisée dans la hiérarchie (c'est-à-dire qu'on ne savait pas s'il était $\Pi^0_1$-complet ou strictement au niveau 2). L'objectif principal de ce travail est de déterminer la position exacte du ZPCP au sein de la hiérarchie arithmétique.

Méthodologie
Les auteurs établissent une chaîne de réductions partant du problème de non-halting des machines de Turing déterministes sur entrée vide, passant par les systèmes de semi-Thue, pour atteindre enfin des variantes du PCP. La méthodologie repose sur plusieurs constructions techniques clés :

1. Systèmes de semi-Thue réversibles : Les auteurs construisent un système de semi-Thue spécifique $S_M$ à partir d'une machine de Turing $M$ donnée. Ce système est conçu pour être à la fois $\Theta$-déterministe et $\Theta$-réversible. La propriété de réversibilité est critique pour la réduction finale au ZPCP, car elle permet de simuler les étapes de calcul dans les directions avant et arrière.
2. Morphismes injectifs et délai borné : Le papier construit des morphismes $g$ et $h$ qui simulent le système de semi-Thue. Une contribution technique significative est la preuve que ces morphismes sont de « délai borné 2 », ce qui implique qu'ils sont injectifs. Cela permet aux auteurs d'étendre les résultats d'indécidabilité à la classe des morphismes injectifs.
3. Variantes décalées : Les auteurs définissent et analysent des variantes de « décalage $s$ » des problèmes ($\omega$PCP$_s$ et ZPCP$_s$), où la condition d'égalité est fixée à un décalage $s$ spécifique. Ils prouvent que ces variantes sont $\Pi^0_1$-complètes.
4. Désynchronisation et surlignage : Pour gérer la nature bi-infinie du ZPCP et éliminer les solutions triviales, les auteurs emploient une construction d'alphabet complexe impliquant des copies surlignées et non surlignées des symboles, ainsi que des marqueurs de « désynchronisation » spécifiques ($d^4$ et $f^4$). Cela force toute solution à alterner entre des configurations vers l'avant et vers l'arrière, simulant efficacement la dérivation du système de semi-Thue dans les deux directions.

Contributions clés et résultats

• Complexité de $\omega$PCP : Les auteurs prouvent que le PCP infini ($\omega$PCP) est indécidable même lorsqu'il est restreint aux morphismes injectifs (spécifiquement, des morphismes de délai borné 2). De plus, ils établissent que cette version restreinte est $\Pi^0_1$-complète.
• Complexité des problèmes décalés : Le papier prouve que pour tout entier naturel $s$, le PCP infini à décalage $s$ ($\omega$PCP$_s$) et le PCP bi-infini à décalage $s$ (ZPCP$_s$) sont $\Pi^0_1$-complets.
• Complexité de ZPCP : Le résultat principal concerne le ZPCP standard. Les auteurs prouvent que le ZPCP est $\Pi^0_1$-dur. Combiné au résultat connu que le ZPCP appartient à $\Sigma^0_2$ et n'est pas dans $\Pi^0_1$, et à la nouvelle preuve qu'il n'est pas dans $\Sigma^0_1$ (en raison de sa $\Pi^0_1$-dureté), ils concluent que :
  $$\text{ZPCP} \in \Sigma^0_2 \setminus (\Pi^0_1 \cup \Sigma^0_1)$$
  Cela place le problème strictement au second niveau de la hiérarchie arithmétique.
• Systèmes de semi-Thue : Le problème de non-terminaison pour les systèmes de semi-Thue $\Theta$-déterministes et $\Theta$-réversibles est montré comme étant $\Pi^0_1$-complet.

Signification et affirmations
Le papier affirme avoir affiné la compréhension du paysage de complexité des variantes du problème de correspondance de Post. Plus précisément :

• Il résout l'ambiguïté concernant la position du ZPCP dans la hiérarchie arithmétique, confirmant qu'il n'est pas $\Pi^0_1$-complet mais réside strictement au niveau 2.
• Il démontre que l'indécidabilité et la $\Pi^0_1$-complétude des variantes infinies persistent même sous des contraintes fortes, telles que l'injectivité et le délai borné, qui sont souvent utilisées pour simplifier les problèmes de décision.
• Les auteurs notent que bien qu'ils aient localisé le ZPCP au niveau 2, la question de savoir s'il est $\Sigma^0_2$-complet reste ouverte.

Le travail repose sur une séquence rigoureuse de réductions, partant du non-halting de la machine de Turing vers la non-terminaison des systèmes de semi-Thue, puis finalement vers les diverses variantes du PCP, en utilisant la réversibilité des systèmes construits pour gérer les contraintes bi-infinites.