Zeitkonstruierbare Funktion

Einfache Sprache

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

Def. Zeitkonstruierbare Funktion

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

n sqrt n ist zeitkonstruierbar

Die Funktion $f: n\mapsto n\sqrt n$ ist zeitkonstruierbar, da eine TM $n\sqrt n$ 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. Berechne $\lfloor n\sqrt n\rfloor$ in binär aus der binären Repräsentation von $n$.

Das läuft in $O(n\log n)$, da

• Schritt 1 $O(n\log n)$ braucht, da $O(\log n)$ für jede Eingabe Position verwendet wird, also das $n$ mal und
• Schritt 2 auch $O(n\log n)$, da die Zahlen eine $O(\log n)$ lang sind.