La définition de la classe NP utilise un mode « existentiel » pour les calculs : un calcul est acceptant s'il existe un choix qui amène en un état d'acceptation. La définition de co-NP en revanche utilise un mode « universel » de calcul : c'est seulement quand tous les choix possibles amènent à un état d'acceptation qu'un calcul est acceptant. Dans une machine de Turing alternante, le mode de calcul alterne entre ces deux modes.
La notion de machine de Turing alternante étend celle de machine de Turing non déterministe. Les états sont de deux types : les états existentiels (notés pour "ou") et les états universels (notés pour "et"). Ainsi, une configuration (c'est-à-dire un état, un mot sur le ruban et une position de la tête) existentielle est acceptante s'il existe une configuration successeur acceptante ; une configuration universelle est acceptante si toutes les configurations successeurs sont acceptantes. Une machine accepte une entrée si la configuration initiale sur cette entrée est acceptante.
Définition formelle
Une machine de Turing alternante (à une bande) est une structure , où :
est un ensemble fini d'états ;
est l'alphabet fini de la bande ;
est la relation de transition ( et pour le déplacement à gauche respectivement à droite de la tête) ;
est l'état initial ;
spécifie le type de chaque état (existentiel ou universel).
Une configuration dans un état q avec est dite acceptante si toutes les configurations accessibles en une étape sont acceptantes, et rejetante si au moins une telle configuration est rejetante. En particulier, elle est acceptante s'il n'y a pas de configurations accessibles. Une configuration avec est dite acceptante s'il existe une configuration accessible en une étape qui est acceptante, et rejetante si aucune configuration accessible en une étape n'est acceptante (ceci est le type de tous les états dans une machine de Turing non déterministe usuelle). En particulier, elle est rejetante s'il n'y a pas de confiurations accessibles. La machine M accepte un mot d'entrée w si la configuration initiale sur w de M (dans laquelle l'état de M est , la tête est sur la case gauche de la bande de lecture et la bande contient w) est acceptante, et rejette le mot si la configuration initiale est rejetante.
Si les calculs se terminent, on peut définir récursivement la notion de configurations acceptantes discutée plus haut. Sinon on utilise le théorème de point fixe de Knaster-Tarski[6].
Coût en temps et espace
Pour déterminer si une configuration d'une machine de Turing alternante est acceptante ou non d'après la définition ci-dessus, il n’est pas nécessaire d'examiner toutes les configurations accessibles depuis la configuration courante. Ainsi, une configuration existentielle peut être étiquetée comme acceptante dès qu'une configuration immédiatement accessible a été trouvée qui elle-même est acceptante. Symétriquement, une configuration universelle est rejetante si une des configurations accessibles en une étape est rejetante.
Une machine de Turing alternante décide l'appartenance à un langage formel en temps si, pour tout mot de longueur , il suffit d'examiner des suites de configurations d'au plus étapes pour déterminer si la configuration initiale est acceptante ou non. Une machine de Turing alternante décide l'appartenance en espace s'il suffit d'examiner des configurations qui ne modifient pas plus de cellules de la bande.
Exemple
On décrit ici une machine alternante pour décider la véracité d'une formule booléenne quantifiée (TQBF) : chaque variable propositionnelle peut être liée à un quantificateur existentiel ou universel. Le problème TQBF est PSPACE-complet et généralise le problème SAT qui est NP-complet. Le problème SAT, lui, peut être vu comme le cas particulier où toutes les variables sont quantifiées existentiellement.
La machine alternante fait des branchements existentiels pour essayer toutes les valeurs possibles d'une variable quantifiée existentiellement, et des branchements universels pour essayer toutes les valeurs possibles d'une variable quantifiée universellement, en procédant de gauche à droite dans l'ordre des variables quantifiées. Après avoir choisi les valeurs de toutes les variables quantifiées, la machine accepte l'entrée si la formule booléenne résultante est évaluée à vraie, et la rejette sinon.
Pour le problème SAT, l'algorithme précédent n'utilise que des branchements existentiels (non-déterminisme classique).
Une telle machine décide l'acceptation d'une formule booléenne quantifiée en temps et en espace .
Classes de complexité
La classe est définie comme la classe de langages formels pour lesquels l'appartenance peut être décidée par une machine de Turing alternante en temps pour une constante ; de même, la classe est la classe des langages pour lesquels lequel l'appartenance peut être décidé par une machine de Turing alternante en espace .
Les classes de complexité suivantes sont définies à partir des machines de Turing alternantes :
, les langages décidables en espace logarithmique
, les langages décidables en temps polynomial
, les langages décidables en espace polynomial
, les langages décidables en temps exponentiel
Ces classes sont similaires aux classes P, PSPACE, et EXPTIME, définies à partir des machines de Turing déterministes. On a les résultats suivants[3] (ici et :
.
Ainsi on a :
Alternance bornée
Les classes de complexité peuvent être raffinées[3],[5] si on limite l'alternance dans les calculs.
Définition
Une machine de Turing alternante avec k alternances est une machine de Turing alternante qui passe d'un état existentiel à un état universel ou vice-versa au plus k−1 fois. Formellement, c'est une machine de Turing dont les états sont divisés en k parties indicées par 1,...,k. Les états dans des parties à indices pairs sont universels, ceux à indices impairs existentiels. Les seules transitions possibles sont vers des états dans des parties d'indices plus grands.
est la classe de fonctions en temps commençant en un état existentiel et alternant au plus fois. Elle est appelée le niveau de la hiérarchie .
est définie de même, mais commençant par un état universel ; c'est le complémentaire de .
est défini de manière similaire pour les calculs bornés en espace.
Exemple
On considère le problème de minimisation de circuits(en) : étant donné un circuit A qui calcule une fonction booléennef et un entier n, déterminer s'il existe un circuit avec au plus n portes qui calcule la même fonction f. Une machine de Turing alternante, avec une seule alternance, commençant dans un état existentiel, peut résoudre ce problème en temps polynomial : elle devine un circuit B avec au plus n portes, puis en passant dans un état universel, elle devine une entrée, et vérifie que la sortie de B pour cette entrée est égale à la sortie de A pour cette même entrée.
Classes
On dit qu'une hiérarchie s'effondre au niveau si tout langage de niveau de la hiérarchie est déjà dans son niveau . Une des conséquences du théorème d'Immerman-Szelepcsényi est l'effondrement de la hiérarchie de l'espace logarithmique à son premier niveau[7].
Hiérarchie polynomiale
Une machine de Turing alternante à k alternances et qui commence dans un état existentiel (respectivement universel) peut décider, en temps polynomial, tous les problèmes de la classe (respectivement de la classe )[8] de la hiérarchie polynomiale.
Extensions
Juraj Hromkovič a proposé une extension les machines de Turing alternantes synchronisés[9], où les calculs se synchronisent. L'objectif est de rapprocher ces machines des calculs parallèles.
Notes et références
↑(en) Ashok K. Chandra et Larry J. Stockmeyer, « Alternation », Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas, , p. 98–108 (DOI10.1109/SFCS.1976.4).
↑(en) D. Kozen, « On parallelism in Turing machines », Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas, , p. 89–97 (DOI10.1109/SFCS.1976.20).
↑L. Stockmeyer et A. Chandra, « Provably Difficult Combinatorial Games », SIAM Journal on Computing, vol. 8, no 2, , p. 151–174 (ISSN0097-5397, DOI10.1137/0208013, lire en ligne, consulté le )
↑(en) Dexter C. Kozen, Theory of Computation, Springer (présentation en ligne), Lecture 7: « Alternation »
↑(en) Neil Immerman, « Nondeterministic space is closed under complementation », SIAM Journal on Computing, vol. 17, , p. 935–938 (DOI10.1137/0217058, lire en ligne [PDF]).
↑Juraj Hromkovič, Juhani Karhumäki, Branislav Rovan et Anna Slovodová, « On the power of synchronization in parallel computations », Discrete Applied Mathematics, vol. 32, no 2, , p. 155–182 (DOI10.1016/0166-218X(91)90098-H, lire en ligne, consulté le )
Bibliographie
Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, , 2e éd., 400 p. (ISBN0-534-95097-3), Section 10.3: Alternation, p. 380–386.