9 Komplexitätstheorie

Turingmaschinen erlauben uns, den Resourcenverbrauch einer Berechnung zu quantifizieren: zum einen die Zeit, also die Anzahl der Schritte, die die Turingmaschine durchführt, bis sie anhält; zum anderen der Speicherplatz, also die Anzahl der Zellen auf dem Band (oder den Bändern), die im Verlauf der Berechnung beschrieben werden. Beides sind Maße, die tatsächlich im echten Leben relevant sind. Turingmaschinen erlauben uns, diese genau zu quantifizieren und die Zeitkomplexität und Speicherkomplexität eines Problems zu untersuchen. In diesem Kapitel werden wir uns zum Großteil auf Zeitkomplexität beschränken.

Es gibt weitere Resourcen, die man mit Turingmaschinen nicht wirklich quantifizieren kann:

I/O-Komplexität. In echten Rechnern haben wir eine Hierarchie von Speichermedien. Den extrem schnellen Prozessorcache; schnellen Cache; den vergleichsweise langsamen Hauptstpeicher (RAM); eventuell sogar einen externen Festplattenspeichern, der um Größenordnungen langsamer ist.
Kommunikationskomplexität. Bei verteilten Anwendungen (Cloud Computing) ist die limitierende Resource eventuell gar nicht die Rechenkapazität sondern das Netzwerk, über das die Daten ausgetauscht werden.

Also: Turingmaschinen sind zwar universell in dem Sinne, dass sie wohl alle physikalisch realisierbaren Rechnermodelle simulieren können (ich sage wohl, weil wir nicht wissen, was alles physikalisch realisierbar ist). Allerdings ist es möglich, dass Sie, abhängig von Ihrem Anwendungsfeld, ein abgewandeltes oder völlig anderes Modell benötigen, um den Resourcenverbrauch modellieren zu können.

Dennoch: in diesem Kapitel beschränken wir uns auf die Resource Zeit, und daher sind Turingmaschinen das Modell der Wahl.

Zeitkomplexitätsklassen

Wir beschränken uns der Einfachheit halber auf das Eingabealphabet $Σ = {0, 1}$ und auf Entscheidungsprobleme, wo uns also nur eine Ja/Nein-Antwort interessiert.

Definition 9.1 Sei $t : N \to N$ . Eine Turingmaschinen $M$ entscheidet eine Sprache $L \subseteq Σ^{*}$ in Zeit $t$ wenn

sie die Sprache entscheidet, also $x \in L ⟺ f_{M} (x) = accept$ und
für jede Eingabe $x$ in maximal $O (t (| x |))$ Schritten terminiert.

Wir definieren nun

\begin{array}{r} {TIME}_{k} (t) := {L \subseteq Σ^{*} | es gibt eine k -Band-TM M, die L in Zeit t entscheidet} \end{array}

und schließlich

\begin{array}{r} TIME (t) := ⋃_{k \geq 1} {TIME}_{k} (t) . \end{array}

Falls Sie sich nicht mehr genau an die $O$ -Notation erinnern können: in diesem Zusammenhang heißt das, dass es Konstanten $c$ und $d$ gibt, so dass $M$ in maximal $c t (| x |) + d$ Schritten terminiert. Die Konstanten $c$ und $d$ dürfen von $M$ abhängen, aber nicht von der Eingabe $x$ oder der Länge $| x |$ . Wir haben in Kapitel 7.3 gezeigt, wie man eine $k$ -Band-Turingmaschine $M$ durch eine Ein-Band-Turingmaschine $M^{'}$ . Der Aufwand war quadratisch: wenn $M$ innerhalb von $t$ Schritten terminiert, so terminiert $M^{'}$ innerhalb von $c t^{2}$ Schritten, wobei $c$ eine Konstante ist, die von $M$ abhängt. Mit unser neuen Notation können wir das sehr konzis schreiben:

Theorem 9.2 ( $k$ -Band zu $1$ -Band). Sei $t : N \to N$ . Dann gilt ${TIME}_{k} (t) \subseteq {TIME}_{1} (t^{2})$ .

Der quadratische Overhead wird tatsächlich störend, wenn man Zeit als Resource untersucht. Daher gibt es eine bessere Simulation; die benötigt allerdings zwei Bänder (Oder drei? Weiß ich gerade nicht exakt) und die Konstruktion ist deutlich komplizierter. Daher vorerst ohne Beweis:

Theorem 9.3 ( $k$ -Band zu $2$ -Band; ohne Beweis). Sei $t : N \to N$ . Dann gilt ${TIME}_{k} (t) \subseteq {TIME}_{2} (t \log t)$ .