Satz von Immerman und Szelepcsényi

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Sei s:\mathbb{N}\rightarrow\mathbb{N} eine platzkonstruierbare Funktion mit s(n)\in \Omega(\log(n)). Dann gilt:

\text{NSPACE}(s(n)) = \text{co-NSPACE}(s(n))

Beweis[Bearbeiten]

Der Beweis verwendet die Beweistechnik des interaktiven nichtdeterministischen Zählens.

Siehe auch[Bearbeiten]