Benutzer:Particle~dewiki/Konstruierbarkeit (Komplexitätstheorie)

Das Attribut der Konstruierbarkeit einer Funktion sagt aus, ob die Funktion

Formale Definition

Bandkonstruierbar

$f:\mathbb {N} \rightarrow \mathbb {N}$ heisst bandkonstruierbar, falls es eine Turingmaschine gibt, so dass

$\forall n.f_{M}(0^{n})=0^{f(n)}$ und

${\tilde {s}}_{M}\in O(f)$ erfüllt ist.

Zeitkonstruierbar

$f:\mathbb {N} \rightarrow \mathbb {N}$ heisst zeitkonstruierbar, falls es eine Turingmaschine gibt, so dass

$\forall n.f_{M}(0^{n})=0^{f(n)}$ und

${\tilde {t}}_{M}\in O(f)$ erfüllt ist.

Zusammenhang von Zeit- und Bandkonstruierbarkeit

Ein wichtes Lemma ist, dass alle zeitkonstruierbaren Funktionen, auch bandkonstruierbar sind. Dies läßt sich leicht beweisen, da eine Turingmaschine in einem Takt das Band nur um eine Position verschieben kann.

Beispiele

Zeit- und damit auch bandkonstruierbar

$f_{1}(n)=n$

$f_{2}(n)=n^{2}$

$f_{3}(n)=n\cdot \log n$

$f_{4}(n)=2^{n}$

Band aber nicht zeitkonstruierbar

$f_{5}(n)=\log {n}$

$f_{6}(n)=\lfloor {\sqrt {n}}\rfloor$

Literatur

Kurs 1564