Raumkonstruierbare Funktion

Einfache Sprache

Eine Funktion $f$ ist raumkonstruierbar wenn eine TM existiert die immer mit $f(n)$ (in binärer Form) für die Eingabe $1^n$ und ein Platzkomplexität von $O(f(n))$ hat. Bei einem Bruch wird abgerundet.

Def. Raumkonstruierbare Funktion

Eine Funktion $f:\mathbb N \to \mathbb N$, wobei $f(n)$ mindestens $O(\log n)$ ist, wird raumkonstruierbar genannt, wenn die Funktion die Zeichenkette $1^n$ auf die binäre (Binärsystem) Representation von $f(n)$ abbildet und dabei in dem Raum $O(f(n))$ läuft.

n^2 ist raumkonstruierbar

Die Funktion $f: n\mapsto n^2$ ist raumkonstruierbar, da eine TM $n^2$ wie folgt für die Eingabe $1^n$ konstruieren kann:

1. Fahre mit dem Lese-Schreib-Kopf über das Band und inkrementiere für jede $1$ einen binären Zähler.
2. Multipliziere den Zähler mit sich selbst.
3. Schreibe das Produkt aufs Ausgabeband.

Das läuft in dem Raum $O(n)$, was wiederum im Raum $O(n^2)$ ist.

Beachte das falls die Raumkonstruierbarkeit für eine Funktion $f(n)$ mit Platzkomplexität $o(n)$ gezeigt werden soll, muss man eine ROITM verwenden wie bei L und NL.