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 $s:\mathbb{N}\rightarrow\mathbb{N}$ eine bandkonstruierbare Funktion mit $s(n)\geq\log(n)$. Dann ist NSPACE(s(n)) = co-NSPACE(s(n)).

Siehe auch

• Liste von Komplexitätsklassen