View
50
Download
0
Category
Preview:
DESCRIPTION
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 - PowerPoint PPT Presentation
Citation preview
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
Recommended