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.

Formale Definition

Sei eine monotone Funktion mit . Dann gilt:

Insbesondere gilt dann . Es gilt aber auch dass aus mit der Paddingtechnik das Theorem für alle folgt.

Beweis

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

Vorbemerkungen

Sei eine Sprache über der Typ-1-Grammatik mit den üblichen Symbolen für Nichtterminale , Terminale , Produktionsregeln und dem Startsymbol . Dann ist für ein Wort der Graph derjenige Graph, der alle Satzformen mit einer Länge höchstens der Länge von enthält, wobei der Graph genau dann eine Kante zwischen zwei Satzformen hat, wenn es eine Produktion in gibt. Insbesondere enthält der Graph sowohl als auch selbst und es gilt, dass genau dann, wenn es einen Pfad von nach 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 nach gibt, ist der Beweis erbracht.

Nicht-Erreichbarkeit

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

Gegeben Graph , Startknoten , Zielknoten und Anzahl erreichbarer Knoten .

  1. Initialisiere Zähler
  2. Für jeden Knoten :
    • Rate nichtdeterministisch, ob von erreichbar ist und falls die Antwort positiv ist:
      • Rate nichtdeterministisch einen Pfad von nach der Länge höchstens und
      • falls der Pfad falsch war oder nicht zu führt, breche mit nein ab,
      • falls , breche mit nein ab (denn der Knoten ist offenbar erreichbar),
      • ansonsten erhöhe den Zähler um eins.
  3. Falls , breche mit nein ab, ansonsten gebe ja aus.

Weder noch können größer als sein und verbrauchen demnach (binär kodiert) nicht mehr als Speicherplatz. Der Algorithmus stellt sicher, dass alle Knoten, die von erreichbar sind, aufgezählt werden und akzeptiert nur dann, wenn keiner dieser Knoten war.

Induktives Zählen

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

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

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

Der Beweis

Nun müssen lediglich beide Algorithmen kombiniert werden.

  1. Berechne für und durch induktives Zählen.
  2. Benutze Nicht-Erreichbarkeit für und mit zuvor berechnetem .

Eine solche Turingmaschine akzeptiert genau dann, wenn es keinen Pfad von nach 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]).