Seminarvortrag über LOG-SPACE

von Rasmus Krause

09.12.04

1. Komplexitätsklassen

Verknüpfung von Log-space Algorithmen

Zusammenhang logarithmischer Zeit und Platz

Erreichbarkeit in gerichteten Graphen ist NL -vollständig

NL = coNL

Das ist das eine Folgerung aus dem

Immerman-Szelepscenyi Theorem:

Für einen Graphen g und einen Knoten x ,

ist die Zahl der von x erreichbaren Knoten

berechenbar von einer

nichtdeterministischen TM mit

logarithmischem Platz.

2-SAT ist NL-vollständig

2-SAT ist NL-vollständig

Erreichbarkeit in ungerichteten Graphen …

kann randomisiert mit logarithmischem Platz berechnet werden

Wie oft wird ein Knoten besucht

Der Algorithmus

Übersicht der Klassen