Machine de Turing alternante

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

Description informelle

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 $\lor$ pour "ou") et les états universels (notés $\land$ 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 $M=(Q,\Gamma ,\delta ,q_{0},g)$ , où :

$Q$ est un ensemble fini d'états ;
$\Gamma$ est l'alphabet fini de la bande ;
$\delta \subseteq Q\times \Gamma \times Q\times \Gamma \times \{\leftarrow ,\rightarrow \}$ est la relation de transition ( $\leftarrow$ et $\rightarrow$ pour le déplacement à gauche respectivement à droite de la tête) ;
$q_{0}\in Q$ est l'état initial ;
$g:Q\to \{\land ,\lor \}$ spécifie le type de chaque état (existentiel ou universel).

Une configuration dans un état q avec $g(q)=\land$ 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 $g(q)=\lor$ 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 $q_{0}$ , 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 $t(n)$ si, pour tout mot de longueur $n$ , il suffit d'examiner des suites de configurations d'au plus $t(n)$ étapes pour déterminer si la configuration initiale est acceptante ou non. Une machine de Turing alternante décide l'appartenance en espace $s(n)$ s'il suffit d'examiner des configurations qui ne modifient pas plus de $s(n)$ 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 $n^{2}$ et en espace $n$ .

Classes de complexité

La classe ${\mathsf {ATIME}}(t(n))$ 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 $c\cdot t(n)$ pour une constante $c>0$ ; de même, la classe ${\mathsf {ASPACE}}(s(n))$ est la classe des langages pour lesquels lequel l'appartenance peut être décidé par une machine de Turing alternante en espace $c\cdot s(n)$ .

Les classes de complexité suivantes sont définies à partir des machines de Turing alternantes :

${\mathsf {ALOGSPACE}}={\mathsf {ASPACE}}(\log n)$ , les langages décidables en espace logarithmique
${\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})$ , les langages décidables en temps polynomial
${\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})$ , les langages décidables en espace polynomial
${\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(2^{n^{k}})$ , 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 $f(n)\geq \log(n)$ et $g(n)\geq \log(n)$ :

${\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})$
${\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))$
${\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2})$ .

Ainsi on a :

${\mathsf {AP}}={\mathsf {PSPACE}}$
${\mathsf {APSPACE}}={\mathsf {EXPTIME}}$
${\mathsf {AEXPTIME}}={\mathsf {EXPSPACE}}$

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.

${\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)$ est la classe de fonctions en temps $f\in C$ commençant en un état existentiel et alternant au plus $j-1$ fois. Elle est appelée le niveau $j$ de la hiérarchie ${\rm {TIME}}(C)$ .

${\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)$ est définie de même, mais commençant par un état universel ; c'est le complémentaire de ${\mathsf {ATIME}}(C,j)$ .

${\mathsf {ASPACE}}(C,j)=\Sigma _{\mathsf {SPACE}}(C)$ 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é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

On dit qu'une hiérarchie s'effondre au niveau $j$ si tout langage de niveau $k\geq j$ de la hiérarchie est déjà dans son niveau $j$ . 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 $\Sigma _{k}^{\rm {P}}$ (respectivement de la classe $\Pi _{k}^{\mathrm {P} }$ )^[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,‎ 1976, p. 98–108 (DOI 10.1109/SFCS.1976.4).
↑ (en) D. Kozen, « On parallelism in Turing machines », Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas,‎ 1976, p. 89–97 (DOI 10.1109/SFCS.1976.20).
↑ ^{a b et c} (en) Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, n^o 1,‎ 1981, p. 114–133 (DOI 10.1145/322234.322243, lire en ligne [archive du 12 avril 2016] [PDF]).
↑ L. Stockmeyer et A. Chandra, « Provably Difficult Combinatorial Games », SIAM Journal on Computing, vol. 8, n^o 2,‎ 1^er mai 1979, p. 151–174 (ISSN 0097-5397, DOI 10.1137/0208013, lire en ligne, consulté le 23 octobre 2017)
↑ ^{a et b} (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 5 (« The polynomial hierarchy and alternation »).
↑ (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,‎ 1988, p. 935–938 (DOI 10.1137/0217058, lire en ligne [PDF]).
↑ (en) Dexter Kozen, Theory of Computation, Londres, Springer-Verlag, 2006, 418 p. (ISBN 978-1-84628-297-3, lire en ligne), Lecture 9: « The Polynomial Hierarchy ».
↑ Juraj Hromkovič, Juhani Karhumäki, Branislav Rovan et Anna Slovodová, « On the power of synchronization in parallel computations », Discrete Applied Mathematics, vol. 32, n^o 2,‎ 29 juillet 1991, p. 155–182 (DOI 10.1016/0166-218X(91)90098-H, lire en ligne, consulté le 17 octobre 2017)

Bibliographie

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 2006, 2^e éd., 400 p. (ISBN 0-534-95097-3), Section 10.3: Alternation, p. 380–386.
(en) Christos Papadimitriou, Computational Complexity, Reading (Mass), Addison Wesley, 1993, 523 p. (ISBN 0-201-53082-1), Section 16.2: Alternation, p. 399–401.
Bakhadyr Khoussainov et Anil Nerode, Automata Theory and its Applications, Springer Science & Business Media, 2012, 432 p. (ISBN 978-1-4612-0171-7, lire en ligne)

Portail de l'informatique théorique

[chasto-1] (en) Ashok K. Chandra et Larry J. Stockmeyer, « Alternation », Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas,‎ 1976, p. 98–108 (DOI 10.1109/SFCS.1976.4).

[kozen-2] (en) D. Kozen, « On parallelism in Turing machines », Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas,‎ 1976, p. 89–97 (DOI 10.1109/SFCS.1976.20).

[alternation-3] {a b et c} (en) Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, n^o 1,‎ 1981, p. 114–133 (DOI 10.1145/322234.322243, lire en ligne [archive du 12 avril 2016] [PDF]).

[4] L. Stockmeyer et A. Chandra, « Provably Difficult Combinatorial Games », SIAM Journal on Computing, vol. 8, n^o 2,‎ 1^er mai 1979, p. 151–174 (ISSN 0097-5397, DOI 10.1137/0208013, lire en ligne, consulté le 23 octobre 2017)

[Arora-5] {a et b} (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 5 (« The polynomial hierarchy and alternation »).

[6] (en) Dexter C. Kozen, Theory of Computation, Springer (présentation en ligne), Lecture 7: « Alternation »

[7] (en) Neil Immerman, « Nondeterministic space is closed under complementation », SIAM Journal on Computing, vol. 17,‎ 1988, p. 935–938 (DOI 10.1137/0217058, lire en ligne [PDF]).

[8] (en) Dexter Kozen, Theory of Computation, Londres, Springer-Verlag, 2006, 418 p. (ISBN 978-1-84628-297-3, lire en ligne), 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, n^o 2,‎ 29 juillet 1991, p. 155–182 (DOI 10.1016/0166-218X(91)90098-H, lire en ligne, consulté le 17 octobre 2017)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]