Voir la source de Théorème d'Immerman-Szelepcsényi

Le '''théorème d'Immerman-Szelepcsényi''' est un [[théorème]] d'[[informatique théorique]], et notamment de la  [[Théorie de la complexité (informatique théorique)|théorie de la complexité]], démontré en 1987 indépendamment par [[Neil Immerman]] et [[Róbert Szelepcsényi]], et qui leur a valu d'obtenir conjointement le [[prix Gödel]] en 1995. Une version simplifiée de ce théorème est [[NL (complexité)|NL]] = [[co-NL]]. 

== Introduction ==
Le théorème concerne la [[complexité en espace]] des calculs effectués par des [[machine de Turing|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]]<math>(s(n))</math> l'ensemble des problèmes qui peuvent être ainsi résolus par une [[machine de Turing non déterministe]] en place au plus <math>s(n)</math> en fonction de la taille <math>n</math> de la donnée, et par co-NSPACE<math>(s(n))</math> 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 <math>s(n)</math>. 

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 ?

== Le théorème ==

Dans sa forme générale, le théorème d'Immerman-Szelepcsényi énonce l'égalité :
:<math>\text{NSPACE}(s(n))=\text{co-NSPACE}(s(n))</math> 
pour toute fonction <math>s(n)\ge\log n</math>. 

Le théorème donne comme cas particulier une preuve positive au « deuxième problème » concernant les [[automate linéairement borné|automates linéairement bornés]], et par là même prouve que l'ensemble des [[langage contextuel|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 (complexité)|NL]] et co-NL. En fait, NL est une abréviation pour  NSPACE<math>(\log(n))</math>, c'est-à-dire  NL = NSPACE<math>(\log(n))</math> et de même 
co-NL=co-NSPACE<math>(\log(n))</math>.
L'énoncé dit : 
:<math>\text{NL}=\text{co-NL}</math>.
Il est apparemment plus faible puisque c'est le cas particulier du premier avec <math>s(n)=\log n</math>, mais un argument, assez fréquemment employé dans cette théorie et  appelé l'{{Lien|trad=padding argument|texte=''argument de remplissage''}} (en anglais ''padding argument''), permet de prouver l'équivalence.

== Démonstrations ==
La démonstration du théorème est qualifiée d'élémentaire mais subtile<ref name=godel>{{en}} [http://www.sigact.org/Prizes/Godel/1995.html Citation du prix Gödel 1995 sur ACM].</ref>. 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<ref>{{Computational Complexity (Papadimitriou)}}.</ref> et de Arora et Barak<ref>{{Computational Complexity (Arora et Barak)}}.</ref>.<!--


---------------
http://oldblog.computationalcomplexity.org/archive/2003_06_01_archive.html#200380198     

    Foundations of Complexity
    Lesson 19: The Immerman-Szelepcsenyi Theorem

    Posted by Lance
    Previous Lesson

    In this lesson we will prove the Immerman-Szelepcsényi Theorem.

    Theorem (Immerman-Szelepcsényi): For reasonable s(n)≥ log n, NSPACE(s(n))=co-NSPACE(s(n)).

    Let M be a nondeterministic machine using s(n) space. We will create a nondeterministic machine N such that for all inputs x, N(x) accepts if and only if M(x) rejects.

    Fix an input x and let s=s(|x|). The total number of configurations of M(x) can be at most cs for some constant c. Let t=cs. We can also bound the running time of M(x) by t because any computation path of length more than t must repeat a configuration and thus could be shortened.

    Let I be the initial configuration of M(x). Let m be the number of possible configurations reachable from I on some nondeterministic path. Suppose we knew the value of m. We now show how N(x) can correctly determine that M(x) does not accept.

    Let r=0
    For all nonaccepting configurations C of M(x)
      Try to guess a computation path from I to C
      If found let r=r+1
    If r=m then accept o.w. reject

    If M(x) accepts then there is some accepting configuration reachable from I so there must be less than m non-accepting configurations reachable from I so N(x) cannot accept. If M(x) rejects then there is no accepting configurations reachable from I so N(x) on some nondeterministic path will find all m nonaccepting paths and accept. The total space is at most O(s) since we are looking only at one configuration at a time.

    Of course we cannot assume that we know m. To get m we use an idea called inductive counting. Let mi be the number of configurations reachable from I in at most i steps. We have m0=1 and mt=m. We show how to compute mi+1 from mi. Then starting at m0 we compute m1 then m2 all the way up to mt=m and then run the algorithm above.

    Here is the algorithm to nondeterministically compute m_i+1 from m_i.

    Let mi+1=0
    For all configurations C
      Let b=0, r=0
      For all configurations D
        Guess a path from I to D in at most i steps
        If found
          Let r=r+1
          If D=C or D goes to C in 1 step
            Let b=1
      If r<mi halt and reject
      Let mi+1=mi+1+b

    The test that r<mi guarantees that we have looked at all of the configurations D reachable from I in i steps. If we pass the test each time then we will have correctly computed b to be equal to 1 if C is reachable from I in at most i+1 steps and b equals 0 otherwise.

    We are only remembering a constant number of configurations and variables so again the space is bounded by O(s). Since we only need to remember mi to get mi+1 we can run the whole algorithm in space O(s).

--------------  
==Esquisse de la démonstration ==

L'énoncé général à prouver est le suivant :
'''Théorème.''' ''Soit <math>s(n)\ge\log n</math> une fonction. Alors'' NSPACE<math>(s(n))</math>=co-NSPACE<math>(s(n))</math>.

La première partie de la démonstration consiste à prouver le cas particulier :

'''Théorème.''' ''On a'' NL=co-NL.

Pour cela, on considère un problème de théorie des graphes appelé le ''problème de la {{Lien|trad=st-connectivity|st-connectivité}}''. Ce problèmes est dans la classe NL, et il est même [[théorie de la complexité (informatique théorique)#classe de complexité|NL-complet]]. Le complémentaire de ce problème est appelé par commodité le problème de la ''{{Lien|trad=st-connectivity|st-non-connectivité}}''. Pour démontrer le théorème, il suffit de prouver que ce problème est également dans la classe NL.

'''Définition.''' Soit G un [[graphe orienté]] à n sommets, et soient s et t deux sommets de G. Le problème de st-connectivité est de déterminer s'il existe un [[Lexique de la théorie des graphes|chemin]] de s à t. Formellement, les problèmes de la st-connectivité et st-non=connectivité sont de classes de problèmes, notées STC et co-STC : et définies comme suit
:STC = <math>\{(G,s,t)</math> :il existe un chemin de <math>s</math> à <math>t</math>  dans <math>G \}</math>.
:co-STC = <math>\{(G,s,t)</math> :il n'existe pas de  chemin de <math>s</math> à <math>t</math>  dans <math>G \}</math>.

On démontre que co-STC est dans NL en construisant un algorithme non déterministe qui, en espace logarithmique, décide si deux sommets <math>s</math> et <math>t</math> donnés sont connectés. Pour que l'algorithme soit correct, deux affirmations doivent être vérifiées : 

* Si les choix non déterministes sont faits « correctement », alors il n'y a pas de chemin de <math>s</math> à <math>t</math>. 
* S'il y a un chemin de <math>s</math> à <math>t</math>, alors aucun choix ne peut conduire l'algorithme à un état d'acceptation.

Voici les idées de base pour la preuve de la deuxième condition. Supposons, en raisonnant par l'absurde, que <math>s</math> et <math>t</math> sont connectés, et que l'algorithme termine dans un état d'aceptation. 

Here are the key ideas of the proof of the second condition. For sake of contradiction assume that ''s'' and ''t'' are connected but the algorithm accepts. To keep the adversary controlling the non-determinism "honest", the algorithm is designed so that if the non-determinism is uncooperative, the algorithm rejects at the end of the ENUMERATE subroutine. Therefore since we assumed that the algorithm accepts, the non-determinism must have been cooperative, which implies by the design of the algorithm that we should have rejected, a contradiction.

Soeit <math>V_i</math> l'ensemble des sommets <math>x</math> du graphe <math>G</math> pour lesquels il y a un chemin de <math>s</math> à <math>x</math> de longueur (nombre d'arcs) au plus <math>i</math>. Ainsi, <math>V_0</math> est composé de s seulement. Soit <math>r_i</math> le nombre d'éléments de <math>V_i</math>. Tout sommet accessible depuis <math>s</math> est dans <math>V_{n-1}</math>. On a donc <math>(G,s,t)\in</math>co-STC exactement si <math>t\notin V_{n-1}</math>. 

-->

== Hiérarchie logarithmique ==

Dans le même article, Immerman démontre, comme corollaire, l'égalité entre la classe NL et la [[LH (complexité)|hiérarchie logarithmique]], c'est-à-dire les langages acceptés par des [[Machine de Turing alternante|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 {{Lien|trad=FO (complexity)#Transitive_closure_is_NL|FO (Fermeture transitive)}}, égalité qu'il établit par la [[complexité descriptive]].

== Notes ==
{{Références}}
{{Traduction/Référence|en|Immerman–Szelepcsényi theorem|514657058  |type=note}}

== Annexes ==
=== Articles connexes ===
* [[Théorème de Savitch]]. Ce théorème établit une relation entre les classes de complexité non déterministe en espace et leur contre-parties déterministes. 

=== Lien externe ===
* Lance Fortnow, [http://oldblog.computationalcomplexity.org/archive/2003_06_01_archive.html#200380198 Foundations of Complexity, Lesson 19: ''The Immerman–Szelepcsenyi Theorem'']. Une autre preuve, sur le Web.

=== Bibliographie ===
;Article originaux
* N. Immerman, ''[http://www.cs.umass.edu/~immerman/pub/space.ps Nondeterministic space is closed under complementation]'', [[SIAM Journal on Computing]] 17, 1988, {{pp.|935–938}}.
* Róbert Szelepcsényi, « The Method of Forced Enumeration for Nondeterministic Automata ». ''[[Acta Informatica]]'' vol. 26, {{n°|3}}, 1988, {{p.|279-284}}. Une prépublication, de titre « The method of [[forcing]] for nondeterministic automata », dans le ''Bulletin de l'EATCS'', vol. 33, 1987, {{p.|96–100}}.

;Manuels
* {{Ouvrage|langue=en|prénom1=Christos H.|nom1=Papadimitriou|titre=Computational Complexity|lieu=Reading (Mass)|éditeur=[[Addison-Wesley]]|année=1993 (réimpression avec corrections 1995)|pages totales=523|passage=151-153|isbn=978-0-201-53082-7|isbn2=0-201-53082-1}}.
* {{Computational Complexity (Arora et Barak)|numéro chapitre=4|titre chapitre=Space Complexity}} {{pp.|91-92}}.

{{palette Théorie de la complexité}} 
{{Portail|Informatique théorique}}

{{DEFAULTSORT:Theoreme d'Immerman-Szelepcsenyi}}
[[Catégorie:Théorème de la théorie de la complexité|Immerman-Szelepcsényi]]