Satz von Immerman und Szelepcsényi
- Satz von Immerman und Szelepcsényi
-
Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NL unter Komplementbildung abgeschlossen ist.
Lange nahm man wie für die Klasse NTIME an, dass NL nicht unter dem Komplement abgeschlossen sei, bis 1988 Immerman und Szelepcsényi unabhängig voneinander den Beweis erbrachten.
Formale Definition
Sei 
eine bandkonstruierbare Funktion mit 
. Dann ist NSPACE(s(n)) = co-NSPACE(s(n)).
Siehe auch
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
Satz von Immerman und Szelepcseny — Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NSPACE unter dem Komplement abgeschlossen ist. Lange nahm man an, dass die Klasse NSPACE genauso wie die Klasse NTIME nicht unter dem… … Deutsch Wikipedia
Satz von Immerman und Szelepcsény — Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NSPACE unter dem Komplement abgeschlossen ist. Lange nahm man an, dass die Klasse NSPACE genauso wie die Klasse NTIME nicht unter dem… … Deutsch Wikipedia
Róbert Szelepcsényi — (* 19. August 1966 in Zilina[1]) ist ein slowakischer Informatiker ungarischer Abstammung. Szelepcsenyi, der Sohn des Musikers Jan Szelepcsenyi (* 1937), bewies als Student an der Comenius Universität in Bratislava 1987[2] unabhängig von Neil… … Deutsch Wikipedia
Gödel-Preis — Der Gödel Preis wird jährlich seit 1993 für herausragende Veröffentlichungen in der theoretischen Informatik von der European Association for Theoretical Computer Science (EATCS) und der Association for Computing Machinery (ACM) Special Interest… … Deutsch Wikipedia
Komplexitätsklasse — Zusammenhang verschiedener Komplexitätsklassen Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine… … Deutsch Wikipedia
NL (Komplexitätsklasse) — In der Komplexitätstheorie bezeichnet NL die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können. NL ist eine Erweiterung der Klasse L, die analog für… … Deutsch Wikipedia
NSPACE — ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik. Dort steht NSPACE(f) für die Platzkomplexitätsklasse der Entscheidungsprobleme, die von einer Nichtdeterministischen Turingmaschine mit Platzbedarf O(f)… … Deutsch Wikipedia
