TIME
Einfache Sprache
Def. TIME
Sei $t:\mathbb N\to \mathbb R^+$ ein Funktion. Die deterministische Zeitkomplexitätsklasse
$$\mathbf{TIME}(t(n))$$ist definiert als die Menge aller Sprachen, die von einer Deterministische Turingmaschine mit Laufzeit Big O $O(t(n))$ entscheidbar sind.
Beispiel Sprache für $\mathbf{TIME}(n^2)$
Gegeben die Sprache $A= \{0^k1^k\mid k\geq 0\}$. Sei $M_1$ die Deterministische Turingmaschine die $A$ entscheidet und wie folgt definiert ist: $M_1 :=$ “Für die Eingabe $w$ tue:
- Laufe über das Eingabeband und reject falls eine $0$ rechts von einer $1$ gefunden wird.
- Wiederhole solang $0$-en und $1$-en auf dem Band vorhanden sind:
- Ersetzte sowohl ein $1$ als auch eine $0$ durch ein Platzhaltersymbol.
- Wenn $0$-en übrig bleiben nachdem alle $1$-en ersetzt wurden oder umgekehrt reject. Sonst falls weder $1$-en noch $0$-en auf dem Band übrig geblieben sind accept”
Die Zeitkomplexität wird für jeden Schritt separat bestimmt: Schritt 1 braucht $2n$, da der Kopf wieder am Anfang des Worts sein soll. Schritt 2.1 kostet $O(n)$. Da der Schritt 2 bis zu $n/2$ mal ausgeführt werden kann, ergibt sich also $(n/2)O(n)=O(n^2)$. Schritt 3 ist wider ein $O(n)$. Zusammen ergibt das $A\in O(n^2)$.
Dann ist
$$A\in \mathbf{TIME}(n^2)$$aber eine Laufzeit von $O(n)$ auf einer 2-Band TM ist möglich.