Platzkomplexität

2018-10-11T09:45:12Z

82.136.84.53: /* Notation */

Unter der '''Platzkomplexität''' eines [[Komplexitätstheorie#Probleme aus Sicht der Komplexitätstheorie|Problems]] versteht man den (minimalen) Bedarf an Speicherplatz eines [[Algorithmus]] zur Lösung dieses Problems, in Abhängigkeit von der Länge der Eingabe. Es interessiert also nicht der Speicherbedarf eines konkreten [[Computerprogramm|Programms]] auf einem bestimmten Computer, sondern vielmehr, ''wie'' der Speicheraufwand wächst, wenn mehr Daten zu verarbeiten sind. Beispielsweise beantwortet die Platzkomplexität die Frage, ob sich der benötigte Speicher bei doppelter Eingabe-Datenmenge verdoppelt oder quadriert (siehe auch [[Skalierbarkeit]]). Sie wird deshalb auch ''Speicherkomplexität'' genannt.

== Notation ==
Die Platzkomplexität wird immer in Bezug auf ein [[Maschinenmodell]] angegeben. In der Regel ist das Bezugsmodell die [[Turingmaschine]]. Es gelten die folgenden Notationen:

* Mit <math>\text{DSPACE}(f)</math> werden alle Probleme bezeichnet, die von einer ''[[Determinismus (Algorithmus)|deterministisch]]en'' Turingmaschine entschieden werden können, die bei einer Eingabe der Länge <math>n</math> höchstens <math>f(n)</math> Speicherzellen für die Berechnung benutzt hat.
* Mit <math>\text{NSPACE}(f)</math> werden alle Probleme bezeichnet, die von einer [[nichtdeterministische Turingmaschine|''nicht-deterministischen'' Turingmaschine]] entschieden werden können, die bei einer Eingabe der Länge <math>n</math> höchstens <math>f(n)</math> Speicherzellen für die Berechnung benutzt hat.

Aus diesen Klassen, lassen sich u. a. folgende Platzkomplexitätsklassen bilden:
* <math>\text{L} := \bigcup_{f \in O(\log(n))}{\text{DSPACE}(f)}</math>
* <math>\text{NL} := \bigcup_{f \in O(\log(n))}{\text{NSPACE}(f)}</math>
* <math>\text{PSPACE} := \bigcup_{f \in O(n^k), k \in \mathbb{N}}{\text{DSPACE}(f)}</math>
* <math>\text{NPSPACE} := \bigcup_{f \in O(n^k), k \in \mathbb{N}}{\text{NSPACE}(f)}</math>

Es gibt darüber hinaus noch weitere Platzkomplexitätsklassen, die sich auf exponentiellen oder gar über-exponentiellen Speicherplatzbedarf beziehen.

== Beziehungen ==
Als echte Teilmengenbeziehung zwischen Platzkomplexitätsklassen deterministischer Turingmaschinen ist <math>\text{L}\subsetneq\text{PSPACE}</math> bekannt.

Die Komplexitätsklassen der [[Zeitkomplexität]] stehen mit denen der Platzkomplexität in folgender Beziehung:

<math>\text{L} \subseteq \text{NL} \subseteq \text{P} \subseteq \text{NP} \subseteq \text{PSPACE} = \text{NPSPACE}</math>

== Sonstiges ==
In der [[Komplexitätstheorie]] ist die Platzkomplexität neben der [[Zeitkomplexität]] ein wichtiges Maß für die „Schwierigkeit“ (oder eben [[Komplexität (Informatik)|Komplexität]]) von Problemen. Die Zeitkomplexität eines Algorithmus kann niemals kleiner sein als dessen Platzkomplexität, da für das Schreiben einer Speicherzelle jeweils ein Rechenschritt benötigt wird.

Formal werden Probleme gemäß ihrer Platzkomplexität oder Zeitkomplexität in [[Komplexitätsklasse]]n eingeteilt.

== Siehe auch ==
* [[Zeitkomplexität]]
* [[Komplexität (Informatik)]]
* [[Effizienz (Informatik)|Effizienz]]
* [[DSPACE]]

{{SORTIERUNG:Platzkomplexitat}}
[[Kategorie:Komplexitätstheorie]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Platzkomplexität