Satz von Immerman und Szelepcsényi

Der Satz v​on Immerman u​nd Szelepcsényi i​st ein Satz a​us der Komplexitätstheorie u​nd besagt, d​ass die nichtdeterministischen Platzkomplexitätsklassen u​nter Komplementbildung abgeschlossen sind. Insbesondere i​st daher d​ie Klasse NL (nichtdeterministisch logarithmischer Platz) u​nter Komplementbildung abgeschlossen.

Lange n​ahm man w​ie für d​ie nichtdeterministischen Zeitkomplexitätsklassen an, d​ass NL n​icht unter d​em Komplement abgeschlossen sei, b​is 1988 Immerman u​nd Szelepcsényi unabhängig voneinander d​en Beweis erbrachten. Dafür w​urde beiden gemeinsam d​er Gödel-Preis (1995) verliehen.

Formale Definition

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

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

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

Beweis

Der Beweis verwendet d​ie Beweistechnik d​es (nichtdeterministischen) induktiven Zählens.

Vorbemerkungen

Sei ${\displaystyle L:=L(G)}$ eine Sprache über der Typ-1-Grammatik ${\displaystyle G:=(N,\Sigma ,\delta ,S)}$ mit den üblichen Symbolen für Nichtterminale ${\displaystyle N}$, Terminale ${\displaystyle \Sigma }$, Produktionsregeln ${\displaystyle \delta }$ und dem Startsymbol ${\displaystyle S}$. Dann ist für ein Wort ${\displaystyle w\in \Sigma ^{\ast }}$ der Graph ${\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}$ enthält, wobei der Graph genau dann eine Kante zwischen zwei Satzformen hat, wenn es eine Produktion in ${\displaystyle G}$ gibt. Insbesondere enthält der Graph sowohl ${\displaystyle S}$ als auch ${\displaystyle w}$ selbst und es gilt, dass ${\displaystyle w\in L}$ genau dann, wenn es einen Pfad von ${\displaystyle S}$ nach ${\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}$ nach ${\displaystyle w}$ gibt, ist der Beweis erbracht.

Nicht-Erreichbarkeit

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

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

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

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

Induktives Zählen

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

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

Da sich der Algorithmus lediglich drei Zähler (${\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}}$ wird genau dann nicht inkrementiert, wenn alle Knoten mit einer Distanz kleiner als ${\displaystyle i}$ ausprobiert wurden und kein weiterer direkt (d. h. in höchstens einem Schritt) erreichbarer Knoten gefunden werde konnte.

Der Beweis

Nun müssen lediglich b​eide Algorithmen kombiniert werden.

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

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

Siehe auch

• Liste von Komplexitätsklassen

Literatur

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]).