DSPACE
Der BegriffDSPACEstammt aus derKomplexitätstheoriein 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 Speicherbedarf 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 zuDSPACE(n).Wenn der Speicherbedarf exponentiell mit der Länge des Eingabewerts wächst, so gehört das Verfahren zuDSPACE(exp(n)).
DSPACE(f) oder auch kurz SPACE(f) steht für die Menge der Raumkomplexitätsklassenin Bezug auf eine deterministischeTuringmaschine.Wird eine konkrete Funktion f angegeben, so bedeutet dies: DSPACE(f) ist die Klasse derjenigenEntscheidungsprobleme,die auf einer deterministischen Turingmaschine mitO(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 SchreibweiseDSPACE(f)wird insbesondere häufig zur Definition konkreterer Komplexitätsklassen verwendet: So ist beispielsweise die wichtige KlassePSPACEwie folgt definiert:
- .
