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 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?