DSPACE

Der Begriff DSPACE stammt aus der Komplexitätstheorie in der theoretischen Informatik. Er liefert eine grundsätzliche Aussage darüber, welchen Speicherbedarf ein Rechenverfahren auf einem idealisierten Modell eines Computers beansprucht. Es lässt sich so also der Speicherdarf für bestimmte Anwendungen abschätzen.

Wenn beispielsweise der Speicherbedarf eines Rechenverfahrens in linearer Proportion mit der Länge des Eingabewerts wächst, so sagt man, das Verfahren gehöre zu DSPACE(n). Wenn der Speicherbedarf exponentiell mit der Länge des Eingabewerts wächst, so gehört das Verfahren zu DSPACE(exp(n)).

DSPACE(f) oder auch kurz SPACE(f) steht für die Menge der Raumkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine. Wird eine konkrete Funktion f angegeben, so bedeutet dies: DSPACE(f) ist die Klasse derjenigen Entscheidungsprobleme, die auf einer deterministischen Turingmaschine mit O(f) Speicherplatz lösbar sind. Man beachte, dass bei Angabe einer konkreten Funktion f die Bezeichnung DSPACE(f) für eine einzelne Komplexitätsklasse steht, während bei Verwendung einer nicht näher definierten Funktion f die Bezeichnung DSPACE(f) eine ganze Menge von Komplexitätsklassen meint. Darüber hinaus sieht man in der Regel von konstanten Faktoren bei der Funktionsdefinition von f ab und setzt somit DSPACE(f) = DSPACE(O(f)).

Die Schreibweise DSPACE(f) wird insbesondere häufig zur Definition konkreterer Komplexitätsklassen verwendet: So ist beispielsweise die wichtige Klasse PSPACE wie folgt definiert:

$\mbox{PSPACE} = \bigcup_{k \ge 1} \mbox{DSPACE}(n^k)$.