Machine de Turing alternante

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer[1] et indépendamment par Dexter Kozen[2] en 1976, avec un article publié en commun en 1981[3]. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs[4]. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale[5].

Définitions[modifier | modifier le code]

Description informelle[modifier | modifier le code]

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[modifier | modifier le code]

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 terminent, on peut définir la notion de configurations acceptantes discutés plus haut récursivement. Sinon on utilise le théorème de point fixe de Knaster-Tarski [6].

Coût en temps et espace[modifier | modifier le code]

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[modifier | modifier le code]

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é[modifier | modifier le code]

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 polynomiale
  • , 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[modifier | modifier le code]

Les classes de complexité peuvent être raffinées[3],[5] si on limite l'alternance dans les calculs.

Définition[modifier | modifier le code]

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[modifier | modifier le code]

On considère le problème de minimisation de circuits (en) : étant donné un circuit A qui calcule une fonction booléenne f 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

  1. (en) Ashok K. Chandra et Larry J. Stockmeyer, « Alternation », Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas,‎ , p. 98–108 (DOI 10.1109/SFCS.1976.4).
  2. (en) D. Kozen, « On parallelism in Turing machines », Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas,‎ , p. 89–97 (DOI 10.1109/SFCS.1976.20).
  3. a, b et c (en) Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, no 1,‎ , p. 114–133 (DOI 10.1145/322234.322243, lire en ligne [PDF]).
  4. L. Stockmeyer et A. Chandra, « Provably Difficult Combinatorial Games », SIAM Journal on Computing, vol. 8, no 2,‎ , p. 151–174 (ISSN 0097-5397, DOI 10.1137/0208013, lire en ligne)
  5. a et b (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 5 (« The polynomial hierarchy and alternation »).
  6. (en) Theory of Computation | Dexter C. Kozen | Springer (lire en ligne)
  7. (en) Neil Immerman, « Nondeterministic space is closed under complementation », SIAM Journal on Computing, vol. 17,‎ , p. 935–938 (DOI 10.1137/0217058, lire en ligne [PDF]).
  8. (en) Dexter Kozen, Theory of Computation, Springer-Verlag, (ISBN 9781846282973), Lecture 9: « The Polynomial Hierarchy ».
  9. 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 (DOI 10.1016/0166-218X(91)90098-H, lire en ligne)

Bibliographie[modifier | modifier le code]