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 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) = Co-NSPACE(S).

Siehe auch

• Liste von Komplexitätsklassen