Théorème d'Immerman-Szelepcsényi

Le théorème concerne la complexité en espace des calculs effectués par des machines de Turing non déterministes. La complexité en espace est mesurée par le nombre de cellules qu'occupent sur la bande les calculs de la machine de Turing. Elle est exprimée en fonction de la taille de l'entrée.

Il est toujours un peu délicat de parler de complexité dans le cas des machines non déterministes puisque, pour une donnée, il peut exister plusieurs, voire une infinité de calculs. D'abord, on ne considère que les calculs qui se terminent. Et parmi ces calculs, celui qui est le plus favorable quant à la mesure que l'on adopte, soit le plus rapide pour une complexité en temps, soit le plus économe en place pour une complexité en espace. Enfin, dans les problèmes qui sont à réponses « oui-non », ce qui est le cas ici, on ne considère que les calculs réussis, qui donc apportent une réponse positive.

On note par NSPACE${\displaystyle (s(n))}$ l'ensemble des problèmes qui peuvent être ainsi résolus par une machine de Turing non déterministe en place au plus ${\displaystyle s(n)}$ en fonction de la taille ${\displaystyle n}$ de la donnée, et par co-NSPACE${\displaystyle (s(n))}$ l'ensemble des problèmes dont le complémentaire qui peut être résolu par une machine de Turing non déterministe en place au plus ${\displaystyle s(n)}$.

Dans le modèle de calcul décrit plus haut, si une machine de Turing apporte une réponse positive en utilisant un certain espace, rien ne garantit a priori que cet espace est suffisant pour apporter une réponse négative à un problème qui n'a pas de solution : il ne suffit pas de considérer les calculs qui ont échoué dans la machine, puisqu'ils peuvent être très volumineux, voire ne pas se terminer sur un ensemble borné de cellules, et alors comment choisir le meilleur ?

Dans sa forme générale, le théorème d'Immerman-Szelepcsényi énonce l'égalité :

${\displaystyle {\text{NSPACE}}(s(n))={\text{co-NSPACE}}(s(n))}$

pour toute fonction ${\displaystyle s(n)\geq \log n}$.

Le théorème donne comme cas particulier une preuve positive au « deuxième problème » concernant les automates linéairement bornés, et par là même prouve que l'ensemble des langages contextuels est fermé par complémentation, une question restée ouverte pendant plus de trois décennies.

Un énoncé équivalent concerne les classes de complexité NL et co-NL. En fait, NL est une abréviation pour NSPACE${\displaystyle (\log(n))}$, c'est-à-dire NL = NSPACE${\displaystyle (\log(n))}$ et de même co-NL=co-NSPACE${\displaystyle (\log(n))}$. L'énoncé dit :

${\displaystyle {\text{NL}}={\text{co-NL}}}$.

Il est apparemment plus faible puisque c'est le cas particulier du premier avec ${\displaystyle s(n)=\log n}$, mais un argument, assez fréquemment employé dans cette théorie et appelé l'argument de remplissage (en) (en anglais padding argument), permet de prouver l'équivalence.

La démonstration du théorème est qualifiée d'élémentaire mais subtile[1]. Le résultat en lui-même est fondamental, et plutôt unique dans la théorie de la complexité. On ne connaît pas de résultat analogue pour la complexité en temps, et il est en général conjecturé que les classes de complexité NP et co-NP sont différentes.

Depuis sa publication, le théorème et sa démonstration font partie du socle de la théorie de complexité, et sont donc enseignés au niveau master, et contenus dans des livres d'enseignement. On peut citer notamment les livres de Papadimitriou[2] et de Arora et Barak[3].

Dans le même article, Immerman démontre, comme corollaire, l'égalité entre la classe NL et la hiérarchie logarithmique, c'est-à-dire les langages acceptés par des machines de Turing alternantes avec accès direct en temps logarithmique et avec un nombre borné d'alternances. Il utilise pour cela l'égalité entre la classe NL et la logique du premier ordre avec fermeture transitive FO (Fermeture transitive) (en), égalité qu'il établit par la complexité descriptive.