Satz von Immerman und Szelepcsényi

Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die nichtdeterministischen Platzkomplexitätsklassen unter Komplementbildung abgeschlossen sind. Insbesondere ist daher die Klasse NL (nichtdeterministisch logarithmischer Platz) unter Komplementbildung abgeschlossen.

Lange nahm man wie für die nichtdeterministischen Zeitkomplexitätsklassen an, dass NL nicht unter dem Komplement abgeschlossen sei, bis 1988 Immerman und Szelepcsényi unabhängig voneinander den Beweis erbrachten. Dafür wurde beiden gemeinsam der Gödel-Preis (1995) verliehen.

Sei ${\displaystyle s:\mathbb {N} \rightarrow \mathbb {N} }${\displaystyle s:\mathbb {N} \rightarrow \mathbb {N} } eine monotone Funktion mit ${\displaystyle s(n)\in \Omega (\log(n))}${\displaystyle s(n)\in \Omega (\log(n))}. Dann gilt:

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

Insbesondere gilt dann ${\displaystyle {\textsf {NL}}={\textsf {co-NL}}}${\displaystyle {\textsf {NL}}={\textsf {co-NL}}}. Es gilt aber auch, dass aus ${\displaystyle {\textsf {NL}}={\textsf {co-NL}}}${\displaystyle {\textsf {NL}}={\textsf {co-NL}}} mit der Paddingtechnik das Theorem für alle ${\displaystyle s(n)\in \Omega (\log(n))}${\displaystyle s(n)\in \Omega (\log(n))} folgt.

Der Beweis verwendet die Beweistechnik des (nichtdeterministischen) induktiven Zählens.

Sei ${\displaystyle L:=L(G)}${\displaystyle L:=L(G)} eine Sprache über der Typ-1-Grammatik ${\displaystyle G:=(N,\Sigma ,\delta ,S)}${\displaystyle G:=(N,\Sigma ,\delta ,S)} mit den üblichen Symbolen für Nichtterminale ${\displaystyle N}${\displaystyle N}, Terminale ${\displaystyle \Sigma }${\displaystyle \Sigma }, Produktionsregeln ${\displaystyle \delta }${\displaystyle \delta } und dem Startsymbol ${\displaystyle S}${\displaystyle S}. Dann ist für ein Wort ${\displaystyle w\in \Sigma ^{\ast }}${\displaystyle w\in \Sigma ^{\ast }} der Graph ${\displaystyle Graph_{|w|}:=((\Sigma \cup N)^{\leq |w|},\alpha \Rightarrow _{G}\beta )}${\displaystyle Graph_{|w|}:=((\Sigma \cup N)^{\leq |w|},\alpha \Rightarrow _{G}\beta )} derjenige Graph, der alle Satzformen mit einer Länge höchstens der Länge von ${\displaystyle w}${\displaystyle w} enthält, wobei der Graph genau dann eine Kante zwischen zwei Satzformen hat, wenn es eine Produktion in ${\displaystyle G}${\displaystyle G} gibt. Insbesondere enthält der Graph sowohl ${\displaystyle S}${\displaystyle S} als auch ${\displaystyle w}${\displaystyle w} selbst und es gilt, dass ${\displaystyle w\in L}${\displaystyle w\in L} genau dann, wenn es einen Pfad von ${\displaystyle S}${\displaystyle S} nach ${\displaystyle w}${\displaystyle w} in diesem Graphen gibt.

Wenn es nun möglich ist, eine nichtdeterministische, linear beschränkte Turingmaschine zu konstruieren, die genau dann akzeptiert, wenn es keinen Pfad von ${\displaystyle S}${\displaystyle S} nach ${\displaystyle w}${\displaystyle w} gibt, ist der Beweis erbracht.

Zunächst sei angenommen, dass die Anzahl ${\displaystyle N}${\displaystyle N} der erreichbaren Knoten von ${\displaystyle S}${\displaystyle S} bekannt ist (wir verschieben die Berechnung von ${\displaystyle N}${\displaystyle N} auf später). Dann löst folgender Algorithmus die Nicht-Erreichbarkeit.

Gegeben Graph ${\displaystyle G=(V,E)}${\displaystyle G=(V,E)}, Startknoten ${\displaystyle s}${\displaystyle s}, Zielknoten ${\displaystyle t}${\displaystyle t} und Anzahl erreichbarer Knoten ${\displaystyle N}${\displaystyle N}.

1. Initialisiere Zähler ${\displaystyle c:=0}${\displaystyle c:=0}
2. Für jeden Knoten ${\displaystyle v\in V}${\displaystyle v\in V}:
   • Rate nichtdeterministisch, ob ${\displaystyle v}${\displaystyle v} von ${\displaystyle s}${\displaystyle s} erreichbar ist und falls die Antwort positiv ist:
     • Rate nichtdeterministisch einen Pfad von ${\displaystyle s}${\displaystyle s} nach ${\displaystyle v}${\displaystyle v} der Länge höchstens ${\displaystyle |V|}${\displaystyle |V|} und
     • falls der Pfad falsch war oder nicht zu ${\displaystyle v}${\displaystyle v} führt, breche mit nein ab,
     • falls ${\displaystyle v=t}${\displaystyle v=t}, breche mit nein ab (denn der Knoten ist offenbar erreichbar),
     • ansonsten erhöhe den Zähler ${\displaystyle c}${\displaystyle c} um eins.
3. Falls ${\displaystyle c<N}${\displaystyle c<N}, breche mit nein ab, ansonsten gebe ja aus.

Weder ${\displaystyle N}${\displaystyle N} noch ${\displaystyle c}${\displaystyle c} können größer als ${\displaystyle |V|}${\displaystyle |V|} sein und verbrauchen demnach (binär kodiert) nicht mehr als ${\displaystyle \log(|V|)}${\displaystyle \log(|V|)} Speicherplatz. Der Algorithmus stellt sicher, dass alle ${\displaystyle N}${\displaystyle N} Knoten, die von ${\displaystyle s}${\displaystyle s} erreichbar sind, aufgezählt werden und akzeptiert nur dann, wenn ${\displaystyle t}${\displaystyle t} keiner dieser Knoten war.

Es bleibt jetzt nur noch die bislang unbekannte Anzahl ${\displaystyle N}${\displaystyle N} der erreichbaren Knoten zu ermitteln. Die Idee ist, die Anzahl ${\displaystyle N_{i}}${\displaystyle N_{i}} der Knoten zu berechnen, die in höchstens ${\displaystyle i}${\displaystyle i} Schritten erreichbar sind. Man lässt ${\displaystyle i}${\displaystyle i} dann induktiv hochzählen und verwendet, dass ${\displaystyle N=N_{|V|}}${\displaystyle N=N_{|V|}} gilt. Der Algorithmus funktioniert wie folgt:

1. Initialisiere ${\displaystyle N_{0}:=1}${\displaystyle N_{0}:=1} (der Startknoten benötigt keinen Schritt um erreicht zu werden)
2. Für jede Anzahl an Schritten ${\displaystyle i=1,\dots ,|V|}${\displaystyle i=1,\dots ,|V|}:
   1. Initialisiere ${\displaystyle N_{i}:=0}${\displaystyle N_{i}:=0}.
   2. ${\displaystyle \star }${\displaystyle \star } Für jeden Knoten ${\displaystyle v\in V}${\displaystyle v\in V}:
      1. Initialisiere einen Zähler ${\displaystyle c:=0}${\displaystyle c:=0}
      2. Für jeden Knoten ${\displaystyle u\in V}${\displaystyle u\in V}:
         • Rate nichtdeterministisch, ob ${\displaystyle u}${\displaystyle u} von ${\displaystyle s}${\displaystyle s} in weniger als ${\displaystyle i}${\displaystyle i} Schritten erreichbar ist.
         • Falls ja, rate einen Pfad von ${\displaystyle s}${\displaystyle s} mit einer Länge kleiner ${\displaystyle i}${\displaystyle i} und breche ab, falls der Pfad nicht in ${\displaystyle u}${\displaystyle u} endet.
         • Falls so ein Pfad gefunden wurde, erhöhe den Zähler ${\displaystyle c}${\displaystyle c} um eins und ...
         • ... wenn ${\displaystyle u}${\displaystyle u} gleich ${\displaystyle v}${\displaystyle v} ist oder es eine Kante von ${\displaystyle u}${\displaystyle u} nach ${\displaystyle v}${\displaystyle v} gibt, erhöhe ${\displaystyle N_{i}}${\displaystyle N_{i}} ebenfalls um eins und setze die Iteration von ${\displaystyle v}${\displaystyle v} fort (markiert mit ${\displaystyle \star }${\displaystyle \star }).
      3. Falls ${\displaystyle c<N_{i-1}}${\displaystyle c<N_{i-1}}, breche die Berechnung ab
3. Gebe ${\displaystyle N_{|V|}}${\displaystyle N_{|V|}} zurück.

Da sich der Algorithmus lediglich drei Zähler (${\displaystyle c,N_{i},N_{i-1}}${\displaystyle c,N_{i},N_{i-1}}) gleichzeitig merken muss, lässt er sich mit logarithmischem Speicherplatz realisieren. Ein formaler Beweis der Korrektheit wird dem interessierten Leser überlassen. Als Beweisidee dient folgender Hinweis: ${\displaystyle N_{i}}${\displaystyle N_{i}} wird genau dann nicht inkrementiert, wenn alle Knoten mit einer Distanz kleiner als ${\displaystyle i}${\displaystyle i} ausprobiert wurden und kein weiterer direkt (d. h. in höchstens einem Schritt) erreichbarer Knoten gefunden werde konnte.

Nun müssen lediglich beide Algorithmen kombiniert werden.

1. Berechne ${\displaystyle N}${\displaystyle N} für ${\displaystyle G:=Graph_{|w|}}${\displaystyle G:=Graph_{|w|}} und ${\displaystyle s:=S}${\displaystyle s:=S} durch induktives Zählen.
2. Benutze Nicht-Erreichbarkeit für ${\displaystyle G:=Graph_{|w|},s:=S}${\displaystyle G:=Graph_{|w|},s:=S} und ${\displaystyle t:=w}${\displaystyle t:=w} mit zuvor berechnetem ${\displaystyle N}${\displaystyle N}.

Eine solche Turingmaschine akzeptiert genau dann, wenn es keinen Pfad von ${\displaystyle S}${\displaystyle S} nach ${\displaystyle w}${\displaystyle w} gibt und da beide Teilalgorithmen nur logarithmischen Speicherplatz benötigen, ist der Beweis komplett.

• Liste von Komplexitätsklassen

Originalpublikationen:

• Neil Immerman: Nondeterministic space is closed under complementation. In: SIAM Journal on Computing. Band 17, Nr. 5, Oktober 1988, S. 935 - 938, doi:10.1137/0217058 . 
• Róbert Szelepcsényi: The method of forcing for nondeterministic automata. In: Acta Informatica. Band 26, Nr. 3, November 1988, S. 279 - 284, doi:10.1007/BF00299636 . 

Lehrbücher:

• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge; New York 2009, ISBN 978-0-521-42426-4, 4.3.2 NL=coNL (Draft [PDF]). 

• Komplexitätstheorie