Platzkomplexität

Einfache Sprache

Def. Platzkomplexität

Sei $M$ eine Deterministische Turingmaschine die auf allen Eingaben hält. Die Platzkomplexität ist die Funktion $f:\mathbb N\to\mathbb N$, wobei $f(n)$ die maximale Anzahl an Speicherzellen, die $M$ auf beliebigen Eingabe der Länge $n$ benutzt. Falls $f(n)$ die Platzkomplexität von $M$ ist, sagen wir auch das $M$ in dem Raum $f(n)$ läuft und das $M$ eine $f(n)$ Platz-Turingmaschine. Normalerweise ist $n$ die Länge der Eingabe.

Zur Quantifizierung der Platzkomplexität dienen die Landau-Symbole.

Def. Nichtdeterministische Platzkomplexität

Sei $M$ eine Nichtdeterministische Turingmaschine die auf allen Eingaben, unabhängig welche nichtdeterministischen Entscheidungen getroffen wurden, hält. Die Platzkomplexität ist die Funktion $f:\mathbb N\to\mathbb N$, wobei $f(n)$ die maximale Anzahl an Speicherzellen, die $M$ auf beliebigen Eingabe der Länge $n$,unabhängig welche nichtdeterministischen Entscheidungen getroffen wurden, benutzt. Falls $f(n)$ die Platzkomplexität von $M$ ist, sagen wir auch das $M$ in dem Raum $f(n)$ läuft und das $M$ eine $f(n)$ Platz-Turingmaschine. Normalerweise ist $n$ die Länge der Eingabe.