die Aussage, daß unter schwachen Voraussetzungen an die Funktion s(n) ≥ ld(n) die Komplexitätsklasse NSPACE(s(n)) (NSPACE) unter Komplementbildung abgeschlossen ist, d. h. mit einer Sprache L gehört auch ihr Komplement zu NSPACE(s(n)).

Im Beweis besteht die Schwierigkeit darin, einen nichtdeterministischen Algorithmus für den Nachweis, daß ein Wort zu einer Sprache gehört, ohne mehr Speicherplatz zu benötigen, in einem nichtdeterministischen Algorithmus für den Nachweis, daß ein Wort nicht zu der Sprache gehört, zu verwandeln.

Als Beweismethode wird induktives Zählen verwendet.