Satz von Immerman und Szelepcsényi

mathematischer Satz

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

Bearbeiten

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.

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

Vorbemerkungen

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Literatur

Bearbeiten

Originalpublikationen:

Lehrbücher: