Komplexitätsklassen

Für eine Menge von Funktionen T:

DTIME(T) bzw. NTIME(T) ist die Klasse aller Sprachen L, für die es eine Funktion t $\in$ T und eine t-zeitbeschränkte deterministische bzw. nichtdeterministische Maschine M gibt mit, die L akzeptiert.

entsprechend DSPACE(s) bzw. NSPACE(s) für Platz-Schranken

Beispiele: für Const = Menge der konstanten Funktionen:

DSPACE(Const): deterministische Maschinen mit endlichem Speicher = endliche Automaten.

Bemerkung: es gilt DSPACE(Const) = NSPACE(Const). Wie heißt dieser Satz im Grundstudium?