On s'intéresse ici à la complexité des problèmes c'est-à-dire aux ressources nécessaires pour les résoudre. Les ressources essentielles sont le temps et l'espace. On ne considère ici que des problèmes décidables. On suppose donc que toutes les machines de Turing considérées s'arrêtent toujours. On étudie l'espace utilisé par les machines de Turing.
Soit M une machine de Turing (a priori non déterministe) et soit w un mot sur l'alphabet d'entrée de M. On suppose que la machine M n'a pas de calcul infini. L'espace d'un calcul de M sur w est le nombre cellules différentes de la bande qui sont utilisées par la machine au cours de ce calcul. C'est aussi la longueur maximale d'une configuration qui apparaît dans ce calcul. L'espace sM(w) utilisé par la machine M sur l'entrée est le nombre maximal de cellules utilisées par un des calculs sur l'entrée w. Si la machine M est déterministe, il n'y a qu'un seul calcul d'entrée w et le temps sM(w) est le nombre de cellules utilisées par ce calcul. Si la machine est non déterministe, l'espace de calcul prend en compte le cas le pire, c'est-à-dire le calcul utilisant le plus de cellules.
En fait, on s'intéresse moins à l'espace de calcul sur une entrée fixée qu'au comportement de la taille de cet espace pour une taille d'entrée donnée. On définit la fonction de complexité en espace sM de M de la manière suivante.
sM(n) = max|w|=n sM(w).
La valeur sM(n) représente l'espace maximal d'un calcul de M avec une entrée de taille n. C'est encore une fois le cas le pire qui est considéré. L'essentiel n'est pas la valeur de sM(n) pour des valeurs précises de n mais le comportement de la fonction sM lorsque n devient grand. On s'intéresse plus au comportement asymptotique de sM qu'à des valeurs particulières.
Pour comparer les comportements asymptotiques des fonctions, on utilise la notation O (grand O). Soit s une fonction de N dans R+. On dit qu'une machine M décide un langage L (et par extension un problème codé par L) en espace s(n) si L est le langage accepté par M et si la fonction de complexité de M vérifie sM = O(s).
On a vu que les différentes variantes de machines de Turing sont équivalentes dans le sens où toute machine d'un modèle peut être simulée par une machine d'un autre modèle. Par contre ces simulations ont une incidence sur l'espace de calcul. On étudie ici le coût du passage d'un modèle à un autre.
Pour la complexité en temps, le passage d'une machine non déterministe à une machine déterministe coûte une exponentielle. Pour la complexité en espace, la situation est différente puisque une machine non déterministe peut être par une machine déterministe qui utilise peu d'espace supplémentaire. Ce résultat étonnant est dû à Savitch.
Théorème (Savitch). Soit s une fonction de N dans R+ telle que s(n) ≥ n pour tout n ≥ 0. Une machine non déterministe qui fonctionne en espace s(n) est équivalente à une machine déterministe qui fonctionne en espace O(s2(n)).
La preuve du théorème consiste à simuler une machine non déterministe M fonctionnant en espace s(n) par une machine M' déterministe fonctionnant en espace s2(n). La machine M' est décrite par un algorithme récursif. La fonction access(C, C', t) ci-dessous retourne vraie si la machine M peut passer de la configuration C à la configuration C' en au plus t étapes de calcul.
access(C, C', t)
if (t ≤ 1)
return C == C' || C ⇒ C'
if (t > 1)
foreach configuration C''
if (access(C, C'', ⌈t/2⌉) && access(C'', C', ⌊t/2⌋))
return true
return false
Pour obtenir l'algorithme global, on suppose que la machine M a un seul état final qf et qu'elle efface sa bande avant de s'arrêter. Lorsqu'elle accepte, sa configuration est nécessairement la configuration Cf = qf où la machine est dans l'état qf, avec la tête de lecture sur la prmière position de la bande et toutes les cases de la bande remplies avec le symbole blanc #.
Soit w une entrée de M de longueur n et soit C0 = q0w la configuration initiale de M avec w. Puisque M fonctionne en espace polynomial, il existe des constantes k et K telles que M fonctionne en temps 2Knk. L'entrée w est acceptée par M si et seulement si l'appel access(C0, Cf, 2Knk) retourne la valeur true. Le nombre d'appels récursifs de la fonction access est borné par Knk et à chaque appel utilise un espace O(nk). L'algorithme fonctionne donc globalement en espace O(n2k).
D'après le théorème Savitch, il n'est pas nécessaire, pour la complexité en espace, de distinguer les machines déterministes des machines non déterministes. Soit t une fonction de N dans R+. On définit la classe SPACE(s(n)) des problèmes qui peuvent être résolus en espace s(n).
SPACE(s(n)) = { L | L peut être décidé en espace s(n) par une machine de Turing déterministe }
La classe importante est celle des problèmes qui peuvent être résolus en espace polynomial. On définit la classe PSPACE de la manière suivante.
PSPACE = ∪k≥0 SPACE(nk)
L'espace utilisé par une machine qui fonctionne en temps t(n) ≥ n est au plus égal à t(n). On a donc les inclusions P ⊆ PSPACE et NP ⊆ NPSPACE = PSPACE.
Si une machine de Turing s'arrête toujours, un calcul de cette machine ne peut pas repasser deux fois par la même configurations. Sinon il existe un calcul infini qui boucle. En effet, le nombre de configurations d'une telle machine est |Q|s(n)ks(n) = 2O(s(n)). Ceci montre qu'une machine qui fonctionne en espace s(n) fonctionne en temps 2O(s(n)). On a donc l'inclusion PSPACE ⊆ EXPTIME.
Les différentes inclusions sont résumées ci-dessous.
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
Le problème d'universalité d'un automate A sur un alphabet Σ est de savoir si l'ensemble des mots acceptés par A est égal à Σ* tout entier, c'est-à-dire L(A) = Σ*. On va voir que la non universalité d'un automate (c'est-à-dire L(A) ≠ Σ*) peut être décidée en espace linéaire par une machine non déterministe. Par le théorème de Savitch, la non universalité et donc aussi l'universalité d'un automate peut être décidée en espace quadratique par une machine de Turing déterministe.
Si l'automate A est déterministe, la solution est facile. En effet A vérifie L(A) = Σ* si et seulement si A est complet et si tout état de A est final.
Le problème est plus difficile lorsque l'automate A n'est pas déterministe. Soit n le nombre d'états de A. L'automate A est équivalent à un automate déterministe ayant au plus 2n états. Si L(A) ≠ Σ*, il existe un mot w de longueur au plus 2n qui n'est pas accepté par A. L'algorithme non déterministe va deviner un mot w tel que |w| ≤ 2n qui n'est pas accepté par A. L'algorithme simule le calcul de A en marquant les états accessibles en lisant le mot w. A chaque étape de calcul, l'algorithme choisit une lettre a de Σ et calcule les états accessibles en effectuant des transitions. Si à une étape, aucun des états accessibles n'est final, le mot w n'est pas accepté et l'algorithme accepte. Après 2n étapes, l'algorithme s'arrête et rejette. L'algorithme utilise un espace linéaire pour stocker le nombre d'étapes effectuées.
On considère des formules booléennes avec des quantificateurs existentiels et universels portant sur ces variables. Ces formules sont donc de la forme
φ = Q1x1Q2x2 … Qnxn ψ
où chaque quantificateur Qi est soit le quantificateur existentiel ∃ soit le quantificateur universel ∀ et où ψ est une formule de la logique propositionnelle ne portant que sur les variables x1, …, xn. Les seuls opérateurs autorisés sont la conjonction, la disjonction et la négation notées respectivement par ∧, ∨ et ¬. Un exemple d'une telle formule est donné ci-dessous.
φ = ∀x ∃y ∀z (x ∧ y) ∨ (x ∨ z)
On appelle formule close une formule booléenne sans variable libre. Le problème QSAT est de savoir si une telle formule close est vraie. Le problème SAT est un cas particulier de QSAT. En effet, une formule ψ portant sur les variables x1, …, xn est par définition satisfiable si la formule φ = ∃x1 … ∃xn ψ est vraie. De même une formule ψ portant sur les variables x1, …, xn est une tautologie si la formule φ = ∀x1 … ∀xn ψ est vraie.
Le problème QSAT est dans la classe PSPACE. En effet, ce problème est décidé par l'algorithme récursif suivant. Pour une formule φ on note φ[x ← b] la formule obtenue en remplaçant la variable x par la valeur booléenne b dans la formule φ.
qsat(φ)
if (φ n'a pas de quantificateur)
return l'évaluation de φ
if (φ = ∃x ψ)
return qsat(ψ[x ← 0]) || qsat(ψ[x ← 1])
if (φ = ∀x ψ)
return qsat(ψ[x ← 0]) && qsat(ψ[x ← 1])
L'algorithme peut être programmé en utilisant une seule copie de la formule φ. Le seul espace supplémentaire nécessaire est pour la pile d'exécution qui est de taille proportionnelle aux nombres de variables quantifiées. L'algorithme fonctionne donc en espace linéaire.
De manière intuitive, un problème est PSPACE-complet s'il est parmi les problèmes les plus difficiles de la classe PSPACE. Plus formellement un problème A est dit PSPACE-complet si les deux conditions suivantes sont remplies.
Si seule la seconde condition est vérifiée, on dit que le problème A est PSPACE-difficile.
Il faut noter que la définition de PSPACE-difficile utilise les réductions en temps polynomial et non pas des réductions en espace polynomial comme cela pourrait sembler a priori naturel. Ce choix se justifie par la nécessité d'avoir des réductions qui se calculent le plus facilement possible. De plus comme PSPACE = NPSPACE, tout problème devient PSPACE-complet si on utilise des réduction en espace polynomial. Il est aussi justifié a posteriori par le résultat suivant qui établit l'existence de problèmes PSPACE-complets.
Théorème. Le problème QSAT est PSPACE-complet.
On a déjà vu que le problème QSAT est effectivement dans la classe PSPACE. Il reste à montrer que tout autre problème de PSPACE se réduit en temps polynomial à QSAT.
La preuve du théorème est similaire à la preuve du théorème de Cook et Levin de la NP-complétude de SAT. L'idée générale est encore d'utiliser des formules pour coder l'existence d'un calcul acceptant dans une machine de Turing.
On suppose donc qu'un problème B est décidé par une machine de Turing M en espace polynomial qu'on peut supposer être nk pour un entier k fixe. Soit w une entrée de M de taille n. L'existence d'un calcul acceptant w est codé de la manière suivante.
Chaque configuration C de la machine M est codée par des variables qui décrivent chacun des symboles de la configuration. Puisque chaque configuration et de taille nk, le nombre de variables nécessaires est au plus O(nk).
Pour deux configurations C et C' et un entier t, on écrit une formule φC,C',t qui est vraie lorsque la machine peut passer la configuration C à la configuration C' en au plus t étapes de calculs. La construction de la formule φC,C',t est semblable à la fonction access utilisée dans la preuve du théorème de Savitch. Dans les deux cas, le cas t = 1 est trivial et le cas t > 1 est résolu de manière récursive.
Pour t = 1, la formule φC,C',1 décrit que C = C' ou que M peut passer de C à C' en exactement une étape de calcul. L'égalité C = C' s'écrit facilement en une formule et le passage de C à C' s'écrit de même manière que cela a été fait dans le théorème de Cook et Levin.
Pour t > 1, on écrit la formule φC,C',t en utilisant le fait qu'un calcul de C à C' en au plus t étapes de calcul passe par une configuration intermédiaire C''. Cette configuration C'' est accessible de C en au plus ⌈t/2⌉ étapes de calcul et C' est à son tour accessible de C'' en au plus ⌈t/2⌉ étapes de calcul. Une première tentative est donc d'écrire la formule φC,C',t de la manière suivante.
φC,C',t = ∃C'' φC,C'',⌈t/2⌉ ∧ φC'',C',⌈t/2⌉
Cette tentative échoue car un calcul de M est de longueur au plus 2Knk pour une constante K fixe. La formule φC,C',t pour t = 2Knk n'est pas de taille polynomial. L'astuce est de remplacer la conjonction des deux formules φC,C'',⌈t/2⌉ et φC'',C',⌈t/2⌉ par une formule qui utilise une seule occurrence de la forme φD,D',⌈t/2⌉. pour des variables D et D' quantifiées universellement.
φC,C',t = ∃C'' ∀ D,D' [(D = C ∧ D' = C'') ∨ (D = C'' ∧ D = C')] ⇒ φD,D',⌈t/2⌉