de.wikipedia.org

Satz von Immerman und Szelepcsényi – Wikipedia

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} } 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.

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

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.

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}:
  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.

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}:
      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.

Nun müssen lediglich beide 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.

Originalpublikationen:

Lehrbücher: