Machine de Turing alternante

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 ${\displaystyle \lor }$ pour "ou") et les états universels (notés ${\displaystyle \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.

Une machine de Turing alternante (à une bande) est une structure ${\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}$, où :

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

Une configuration dans un état q avec ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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].

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 ${\displaystyle t(n)}$ si, pour tout mot de longueur ${\displaystyle n}$, il suffit d'examiner des suites de configurations d'au plus ${\displaystyle 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 ${\displaystyle s(n)}$ s'il suffit d'examiner des configurations qui ne modifient pas plus de ${\displaystyle s(n)}$ cellules de la bande.

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.

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

${\displaystyle {\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 ${\displaystyle {\mathsf {ATIME}}(C,j)}$.

${\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{\mathsf {SPACE}}(C)}$ est défini de manière similaire pour les calculs bornés en espace.

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.

On dit qu'une hiérarchie s'effondre au niveau ${\displaystyle j}$ si tout langage de niveau ${\displaystyle k\geq j}$ de la hiérarchie est déjà dans son niveau ${\displaystyle 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].

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 ${\displaystyle \Sigma _{k}^{\rm {P}}}$ (respectivement de la classe ${\displaystyle \Pi _{k}^{\mathrm {P} }}$)[8] de la hiérarchie polynomiale.