date-created: 2024-06-27 10:40:07 date-modified: 2024-06-27 02:18:22

Komplexität

anchored to 112.00_anchor_overview proceeds from 112.21_rekursive_funktionen aber auch 112.19_unentscheidbare_probleme

Overview

Bis dato haben wir uns nur Bereiche angeschaut, wo wir evaluieren wollten, ob man es überhaupt berechnen konnte. Sofern man einfach beliebig viel Zeit und auch Speicher hat.

Dabei hatten wir dann die drei Strukturen definiert:

$R$ 112.03_reguläre_sprachen
$RE$ 112.15_abzählbarkeit
$\overline{RE}$ 112.16_nicht_erkennbar_entscheidbar und dafür hatten wir auch diverse Beispielfragen definiert, die als Beispiele dafür dienen.

Motivation

Wir möchten folgend auch auf Zeit und Speicher achten und darin dann Komplexität betrachten / definieren und evaluieren.

[!Tip] Motivation

Wir wollen innerhalb der berechenbaren Problemen $\in R$ dann evaluieren, wie effizient man eine Lösung für ein Problem $P$ bestimmmen kann!

Was wir hierbei auch sehen werden:

Es gibt Probleme, die man effizient lösen kann $P$
aber auch Probleme, die man nicht effizient prüfen kann $NP$ –> Dabei werden wir erfahren, dass diese Menge nicht zwingend getrennt voneinander ist, wie es etwa bei $RE / C o RE$ ist!

Beispiel | Komplexität betrachten:

[!Req] Beispielsprache

Wir betrachten folgende Sprache, bei welcher wir folgend den Speicher und die Zeit ( bzw. erstmal die Schritte, die sie brauch) evaluieren wollen!

$L = {0^{k} 1^{k} ∣ k \geq 0}$

Wir wissen, dass sie entscheidbar / berechenbar ist!

Wie viele Schritte benötigen wir hier mindestens um Eingaben zu verarbeiten? Was benötigen wir, um es passend anzusetzen? #card

wir sehen hier, dass die Zahl der Schritte davon abhängt, wie groß die Eingabe $n$ ist!

Ferner müssen wir hier mehr oder weniger eine konkrete Turingmaschine betrachten, um das genau bestimmen zu können –> damit wir ein Gefühl bekommen ,wie eine Eingabe verarbeitet wird.

betrachten wir also eine Turingmaschine $M$ : Auf Eingabe $∣ w ∣= n$ arbeitet sie folgend:

Fahre das Band ab, $re j ec t$ wenn irgendwo eine 0 nach einer 1 kommt ( also invalide Struktur)

$w hi l e$ 0er und 1er auf dem band sind, machen wir folgendes:

Fahre das band ab, streiche genau eine 0 / 1 ab

fahre dann bis zum Beginn der 1 / 0 und streiche auch genau da eine 0 / 1 weg

fahre wieder zurück und wiederhole den Prozess, bis keine Zahl mehr übrig ist.

accept –> wenn nichts übrig ist am Ende

reject –> wenn am Ende noch 1 oder 0 übrig sind ( also sie sind ungleich!)

Damit haben wir also folgende Quantitäten an Schritten (approximiert!): $O (n) + O (n^{2}) + O (n) = O (n^{2})$

Wir sehen hier, dass wir die landau-Notation benötigen! Siehe hier

111.04_laufzeitanalyse_onotation

[!Attention] Unterschiede von det / non-det TMs bei Komplexität

Wir werden hier sehen, dass Turingmaschinen zwar äquivalent in der Entscheidung von Problemen sind ( also genau das gleiche können), aber in der Zeitkomplexität und der Speicherkomplexität divergieren / nicht gleich sind!

Wir wollen aus dieser Betrachtung dann zwei folgende Komplexitäten definieren:

Zeitkomplexität:

[!Definition]

Sei $M$ eine deterministische Einband-Turingmaschine über einem Eingabealpabet $Σ$ , die immer anhält (berechnet also etwas!)

Wir zählen die Schritte dann mit folgender Notation: $t_{M} (x)$ für die Anzahl der Schritte, die die Tm $M$ auf dem Input $x$ durchläuft, bis sie anhält!

Wie können wir dann die Zeitkomplexität besteimmen? #card

Wir bezeichnen dann die Zeitkomplexität bzw auch die Laufzeit von $M$ mit : $T im e_{M} : N \to N; T im e_{M} (n) = max {t_{M} (x) ∣ x \in Σ^{*}, ∣ x ∣= n}$ –> es ist also die maximale Anzahl von Schritten, die $M$ auf allen Inputs der Länge $n$ durchläuft

Speicherkomplexität:

[!Definition]

Sei $M$ wieder eine deterministische Einband-Turingmaschine über einem Eingabealphabet $Σ$ , die immer anhält.

Ferner beschreiben wir jetzt mit $S_{M} (x)$ die Menge der Zellen auf dem Band, auf denen $M$ auf dem Input $x$ operiert - die sie benutzt - bis sie anhält.

Wie können wir damit jetzt die Speicherkomplexität beschreiben? #card

Für eine TM $M$ beschreiben wir die Speicherkomplexität als Funktion: $Sp a c e_{M} : N \to N, Sp a c e_{M} (n) = max {s_{M} (x) ∣ x \in Σ^{*}, ∣ x ∣= n}$

–> also wir suchen die maximale Zahl von Zeilen, die eine TM bei dieser Berechnung verwenden könnte.

“ $M$ läuft dann also in $s p a ce f (n)$ ”

Achtung: Es müssen hier auch leere Zellen, solche, die durchlaufen, aber nicht beschrieben werden, mitgezählt werden, weil man sonst leere Zellen zum kodieren nehmen könnte, um Werte zu repräsentieren –> Dadurch würde man quasii “keinen Speicher” verwenden!

Da wir hier jetzt quantifizieren können, wie schnell (oder wie viel Speicher) eine Turingmaschine für ein berechenbares Problem brauch, können wir ferner Schranken bestimmen, die durch diverse Tms, die das gleiche Problem betrachten / lösen.

[!Definition] Obere Schranken

Sei $L$ eine Sprache. Wir sagen, dass die Funktion $g : N \to N, g (n)$ eine obere Schranke für die Zeitkomplexität von $L$ ist, falls folgendes gilt:

Was muss gelten? Wie können wir das dann formal beschreiben? $\exists M : \dots$ #card

Es muss gelten, dass es eine deterministische TM $M$ gibt, welche $L$ entschiedet, sodass $T im e_{M} (n) \in O (g (n))$ ist.

Also formal:

$\exists M : T im e_{M} (n) \in O (g)$ , und ferner dann:

$\exists M : max_{∣ w ∣= n} t_{W} (w) \in O (g)$ und somit dann schlussendlich:

$\exists M : \exists c > 0, \forall w : ∣ w ∣= n : t_{M} (n) \leq c \cdot g (n)$

Somit folgt also: $L$ hat Zeitkomplexität höchstens $g (n)$ , wenn es eine DTM $M$ gibt, deren Rechenzeit auf jeder Eingabe der Länge $n$ nicht länger als $c \cdot g (n)$ ist! (Wir haben also einen maximalen Wert gefunden, welcher nicht weiter überschritten wird / werden kann)

[!Definition] Untere Schranken

Sei $L$ eine Sprache. Wir sagen, dass die Funktion $g : N \to N, g (n)$ eine untere Schranke für die Zeitkomplexität von $L$ ist, falls folgendes gilt:

Was muss gelten? Wie können wir das dann formal beschreiben? $\exists M : \dots$ #card

Es gilt, falls für jede det Tm $M$ die $L$ entscheidet,, gilt, dass $T im e_{M} (n) \in Ω (g (n))$ ist!

Also formal:

$\forall M : T im e_{M} (n) \in Ω (g)$ und somit

$\forall M : max_{∣ w ∣= n} t_{M} (w) \in Ω (g)$ und somit also

$\forall M : \exists c > 0, \exists w, ∣ w ∣ = n : t_{M} (n) \geq c \cdot g (n)$

Es folgt also:

$L$ hat die Zeitkomplexität $g (n)$ , wenn jede $D TM$ $M$ auf dem schwierigsten Wort der Länge $n$ mindestens $c \cdot g (n)$ braucht

Folgerungen

Wir wollen jetzt aus den obigen Definitionen einige Folgerungen / Lemma / betrachten, die für die weitere Betrachtung praktisch sind / sein können:

Wir wollen zuerst herausfinden, dass es trivial ist, wie das Arbeitsalphabet konstruiert / gegeben ist.

Arbeitsalphabet macht keinen Unterschied

[!Lemma] Behauptung

Sei $f : {0, 1}^{*} \to {0, 1}^{*}$ eine Funktion, die von einer TM $M$ mit einem Arbeitsalphabe $Σ$ in der Zeit $T im e_{M} (n)$ berechnet werden kann.

Wieso ist es jetzt trivial, welches Alphabet $Σ$ wir verwenden? Wie können wir zu einem anderen konvertieren? #card

Wir können jetzt etwa das vorhandene Alphabet $Σ$ in ein anderes $\overline{Σ^{*}}$ konvertieren ( wir kodieren jeden Buchstaben um in eine andere Grundlage)

Wir können durch diese Umrechnung dann die neue Zeit bestimmen: $T im e_{\hat{M}} (n) = \frac{lo g _{2} ∣ Σ ∣}{lo g _{2} ∣ Σ ∣} \cdot T im e_{M} (n)$

Beweisen könnte man das mit folgendem Ansatz:

Wir kodieren alle Buchstaben $\in σ$ mit $lo g_{2} ∣Σ∣$ binären bits, und verwenden dann die Buchstaben $\overline{Σ}$ dann, um sie zu repräsentieren

Es folgt dadurch dann:

Wenn $f$ auf $M$ in $O ((g (n)))$ berechenbar ist dann ist es auch $\overline{M}$

Lemma | Arbeitsalphabet umkodieren

[!Satz]

Es gilt: Für jede $k$ -Band TM $M$ existiert eine $k$ -Band Tm $\hat{M}$ , sodass $L (M) = L (\hat{M})$ und ferner folgt noch ein Bezug zur Zeit und Platz-Komplexität!

Was folgt aus dieser Aussge für $Sp a c e_{\hat{M}} (n)$ und $T im e_{\hat{M}} (n)$ ? #card

Aus obiger Betrachtung folgt ferner noch: $Sp a c e_{\hat{M}} (n) \leq \frac{Sp a c e _{M} ( n )}{2} + 2$

und für die Zeitkomplexität folgt: $T im e_{\hat{M}} (n) \leq \frac{T im e _{M} ( n )}{2} + 2 n$

Woher kommt $+ 2 N$ ? –> Zu Beginn der TM müssen wir die Eingabe zu unserem neuen Alphabet umkodieren! und somit durchlaufen wir es komplett und schreiben die Eingabe um.

Beweis Idee:

Sei jetzt etwa $Γ_{M}$ das Arbeitsalphabet von $M$ . Dann wählen wir jetzt eine neue Struktur $Γ_{\hat{M}} = Γ_{M} \times Γ_{M}$ . Falls $α_{1}, α_{2}, \dots, α_{m}$ der Inhalt des $i$ -ten Bandes von $M$ ist und der Kopf auf $α_{j}$ zeigt, enthält das $i$ -te Band von $\hat{M}$ dann folgendes Wort: $[> α_{1} α_{2} >] [> α_{3} α_{4} >] \dots$

(Falls $m$ etwa ungerade ist , fügen wir einfach ein Leerzeichen am Ende hinzu (padding quasi)) -> Der Kopf zeigt dann immer auf das Tupel, dass $a_{j}$ enthält.

Verwenden wir dann diese Zustand, um zu kodieren, ob dieser Buchstabe das erste oder zweite Symbol im Typel ist.

–> Die Speicherkomplexität ist damit höchstens $1 + ⌈ \frac{Sp a c e _{M} ( n )}{2} ⌉ \leq 2 + Sp a c e_{M} (n) /2$

–> Das gleiche gilt dann auch für die Rechenzeit, allerdings muss man am Anfang einmal das Band abfahren und es umkodieren –> einmal hin und wieder zurück

[!Attention] Es macht wenig Sinn über multiplikative Konstanten zu streiten, da man sie weg-canceln kann

[!Tip]

Wir stellen fest, dass es scheinbar keinen großen Unterschied macht, wenn man das Arbeitsalphabet $Σ$ in ein anderes $\overline{Σ}$ konvertiert und dann die TM verwendet –>

Daher verwenden wir die O-Notation, damit wir solche Modifikationen einfach inkludieren und nicht extra Betrachten müssen!

Notwendigkeit der polynomiellen Laufzeit

[!Bsp]

Wir sehen, dass die Implementierung der TM, für eine beliebige entscheidbare Sprache meist nicht soo relevant ist, weil wir gleich sehen werden, dass man sie mit einer Universellen TM umsetzen und damit eine maximale Grenze nicht überschritten wird.

Ferner, durch die obigen Sätze, können wir aussagen, dass die meisten TMs $M$ - in verschiedenen Strukturen - darauf reduziert werden können.

Beidseitig offfene Bänder

write-only Bänder

random-access Bänder –> sofern das Anfahren einer Speicheradresse $O (L \overset{a}{¨} nge des bandes)$ ist –> das band durch die Laufzeit beschränkt.

Komplexität der Universellen Turingmaschine

112.14_universal_turing_machine

[!Beweis] Satz | Beschreibung einer Effizienten Universellen Turingmaschine

Sei jetzt $f$ eine Funktion, die von einer TM $M$ in gegebener Zeit $T (n) = T im e_{M} (n)$ berechnet werden kann –> das heißt $M$ hält auf $w$ nach spätestens $T (n =∣ w ∣)$ Schritten

Dann sagen wir jetzt: Es existiert eine UTM $U$ , welche die gleiche Funktion in der Zeit $C \cdot T (n) lo g (T (n))$ - also nach dieser Menge von Schritten, also in $O (T (n) lo g T (n))$ berechnet.

Dabei ist $C$ von der Größe des Arbeitsalphabetes $M$ , der Menge von Bändern und der Größe des Zustandsraumes abhängig ist –> also es wird eine Konstante sein, die wir betrachten / anwenden können.

Wie können wir jetzt so anpassen, dass wir auf $O (T^{2})$ reduzieren können? Wie konstruieren wir es entsprechend? #card

Wir wollen jetzt die einfachere Variante beweisen, dass $O (T^{2})$ erhalten wird, statt dem $O (T lo g (T))$ (den weiteren Schritt argumentieren wir einfach)

Wir nehmen an, dass $M$ nur ein Band hat - falls nicht, können wir es ja in $O (T^{2})$ transformieren ( Wir wenden ferner $Σ = {0, 1}$ als Alphabet an ( weil wir ja alles damit kodieren können))

Wir erinnern uns an die universelle Turingmaschine, welche 3 Bänder hatte ( 1. Simulation von $M$ , 2. Gödelnummer (also Programm) von $M$ speichern; 3. speichert den aktuellen Zustand von $M$ (Simuliert))

–> Jeder Schritt von $M$ kostet nur $C$ overhead afu den anderen beiden Bändern –> wobei $C$ ja von den Parametern: $∣ Q ∣, ∣Γ∣$ abhängt ( wenn die Übergänge von $M$ betrachtet, bildet es hier eine Matrix!)

Damit haben wir also maximal $O (T^{2})$ erzeugt!

Man kann diese Struktur jetzt noch von $O (T^{2})$ auf $O (T lo g T)$ verkürzen:

–>die $k$ Bänder kann man effizienter Kodieren

Wir speichern alle Bänder in einem Zustand $\in Γ^{k}$ . ProblemL Die Köpfe auf den Bändern können sich ja unabhängig verschieben. –> Wenn das passiert brauchen wir irgendwie einen Shift der Bänder relativ zueinander –> Das kann man mit einer geschickten Codierung realisieren! ( Kodiere die Zahl der Shifts selbst, in $lo g ∣ S hi f t s ∣$ )

Das geht durch amortisierte Laufzeitanalyse

Folgerung

Durch diese Konversion / Betrachtung in verschiedenen Varianten - wir aber immer auf die gleiche zurückkommen - können wir jetzt Aussagen über Probleme treffen:

Im folgenden werden wir also den Fokus darauf setzen, dass ein Problem in polynomieller Laufzeit lösbar ist.
Es ist somit irrelevant, wie die TM implementiert wird!

[!Attention] Was nicht egal ist:

Es ist nicht egal, ob die Turingmaschine deterministisch ist / oder nicht

–> Obwohl sie in der Berechenbarkeit gleich sind, ist ihre Zeit / Platz-Komplexität nicht gleich –> bei einer Det ist sie meist sogar exponentiell größer!

Laufzeit- und Speicherkomplexität | Klassen

Wir können jetzt ferner Klassen für die Zeit- und Speicherkomplexität definieren:

Komplexitätsklasse TIME

[!Definition]

Sei $T : N \to N$ eine Zeit-Komplexitäts-angabe

Wir wollen daraus jetzt die Komplexitätsklasse $T I ME (T (n))$ bestimmen:

Wie wird sie definiert, was enthält sie? #card

Die Komplexitätsklasse $T I ME (T (n))$ ist die Menge aller Sprachen $L \subseteq {0, 1}^{*}$ , die in worst-case Laufzeit $O ((T (n)))$ von einer deterministischen Turingmaschine entschieden werden können.

Wir beschreiben die Menge dann folgend: $T I ME (T (n)) = {L \subseteq {0, 1}^{*} ∣ \exists DTM M, die L entscheidet und weiterhin T im e_{M} (n) \in O ((T (n)))}$

Komplexitätsklasse SPACE

[!Definition]

Sei $S : N \to N$ eine Speicherplatz-Komplexitäts-angabe

Wir wollen daraus jetzt die Komplexitätsklasse $SP A CE (S (n))$ bestimmen:

Wie wird sie definiert, was enthält sie? #card

Die Komplexitätsklasse $SP A CE (S (n))$ ist die Menge aller Sprachen $L \subseteq {0, 1}^{*}$ , die in worst-case Laufzeit $O ((S (n)))$ von einer deterministischen Turingmaschine entschieden werden können.

Wir beschreiben die Menge dann folgend: $SP A CE (S (n)) = {L \subseteq {0, 1}^{*} ∣ \exists DTM M, die L entscheidet und weiterhin Sp a ce M (n) \in O ((S (n)))}$

–> Also alle TMs, die genau die gleiche Speicherkomplexität aufweisen!

Daraus kann man jetzt die $P$ Komplexitätsklasse bestimmen!

Komplexitätsklasse P

[!Definition]

Wir wollen die Menge von Sprachen, die in polynomieller Zeit det. entschieden werden können.

Dafür definieren wir $P = ⋃_{k \in N} T I ME (n^{k})$

was beschreibt sie? #card

Diese neue Menge $P$ enthält also alle Sprachen, die in polynomieller Laufzeit von einer deterministischen Turingmaschine entschieden werden können

(Bedenke, dass Polynom sich in der Betrachtung der Laufzeit immer auf den größten Grad reduziert)

Komplexitätsklasse PSPACE

[!Req] Definition PSPACE

Wir wollen noch die Menge von Sprachen, die einen polynomiellen Speicherbedarf haben, beschreiben / als Menge zusammenfassen.

Wie definieren wir diese Menge PSPACE? #card

Die Menge wird folgend beschrieben: $PSP A CE = k \in N ⋃ SP A CE (n^{k})$

–> Heißt also, dass sie alle Sprachen inkludiert, die mit einem polynomiellen Speicherbedarf von einer det. Turingmaschine entschieden werden können.

TIME $\subseteq$ SPACE

[!Req]

Für jede Funktion $t : N \to R^{+}$ gilt folgend:

$T I ME (t (n)) \subseteq SP A CE (t (n))$ (Bedenke, dass $SP A CE$ , $T I ME$ die Komplexitätsklassen beschreibt, die alle TMs aufweist, die die Größe hat)

Das kommt daher, dass jede $TM$ (det!), die in der Zeit $T im e_{M} (n)$ arbeitet, nicht mehr als $T im e_{M} (n)$ Felder beschreien kann.

Es gilt also $Sp a c e_{M} (n) \subseteq T im e_{M} (n)$ für jede DTM $M$ (Bedenke, dass $Sp a ce$ , $T im e$ die Komplexität für eine spezifische Tm beschreibt (also für eine beliebige TM!))

Hierbei ist die Frage, warum die Ungleichheit bei einzelnne BSp genau anders war.

In $N$ schritten können wir höchstens $n$ Schritte beschreiben.

Wir beschränken uns hierbei nach unten, weil wir eine maximale Grenze setzen, ferner aber auch weniger angewandt / verwenedet werden kann! –> Damit haben wir also eine Grenze nach oben hin, aber können natürlich auch kleinere Werte erhalten, die die Komplexität verursachen!

Bemerkungen

Konkret haben wir hier ein Entscheidungsproblem beschrieben, denn man kann hier enweder angeben, ob:
- es einen kürzesten Pfad von $A \to B$ gibt oder nicht (ja / nein!)
- Was ist der Wert der Funktion $f : X \to> Q$ am Punkt $x \in X$
- Welcher Input $x$ minimiert den Wert der Funktion $f$ ?

Solche Probleme kann man meist auf ein Entscheidungproblem reduzieren oder es mit diesem approximieren, weil endliche Mengne durch Binärzahelen in logarithmischer Komplexität -> Länge der Binärzahl / Anzahl der entscheidungsprobleme <- adresssierbar sind!

[!Example]

Wir stellen die Frage: “Was ist die Länge des kürzesten Weges von $A \to B$ ”?

Diese Frage können wir umstellen, sodass man hier auch ein entscheidungsproblem betrachtet -> was sich aber Schritt für Schritt an die Lösung hinarbeitet ( also versucht nach und nach dem kürzesten Pfad naher zu kommen!).

Wir stellen die Frage folgend um:

Gibt es einen Weg kürzer $T$ ?

Gibt es einen Weg kürzer als $\frac{T}{2}$

oder $\frac{T}{4}$

$\dots$

–> Also immer die gleiche Frage, aber wir werden in der Länge immer kleiner!

All diese Fragen werden nach logarithmisch vielen Schritten konvergieren und somit wird die polynomielle Laufzeit nicht wirklich veränder –> Man kann es also gleich formulieren / das gleiche Meinen!

Fokus lag auf theoretische Turingmaschinen

Wir haben diese obige Definition primär so gesetzt, dass wir uns auf Turingmaschinen bezogen haben.

Dass wir diese Struktur nun auch auf reale Maschinen anwenden kann, ist logisch, da sie ähnlich funktionieren, auch wenn sie eine spezifischerre Konstruktion / Architektur aufweisen!.

[!Tip] Theoretische Übersetzung von TM -> praktische Implementation

Betrachten wir ein Beispiel:

Sei $G = (V, E)$ ein Graph, und die Frage, ob er zusammenhängend ist –> Entscheidungsproblem!

Wie gehen wir jetzt vor, um für eine TM die Komplexität zu beschreiben, wie können wir das aber unter praktischer Betrachtung ebenfalls lösen? #card

Formal müssten wir hier eine TM $M$ mit Input $w (G)$ konstruieren, die bits $n = ∣ w ∣$ des inputs zählt und die Zahl der Rechenschritte von $M$ zählen muss / wird.

Praktisch: ( bezieht sich auch viel auf 111.00_anchor) wir haben eine bessere / praktischere Lösung beschrieben:

setzen wir $n = ∣ K n o t e n ∣ + ∣ K an t e n ∣$

definiere Algorithmus, welcher die Zahl $F (n)$ der arithmetischen Operationen im Algorithmus zählt ( also er kann abhängig von $n$ sagen, wie viele Schritte wir brauchen werden!)

Anschließend zeigen wir dann noch $F (n) \in O (n^{d})$

Diese Struktur ist formal nicht ganz gleich.

–> Es wird hier eine von Neumann Architektur (RAM).

Wir wissen, dass RAMs turing äquivalent und somit kann man diese RAM-Konstruktion dann auch mit einer TM in linearer Zeit darstellen kann.

Further Resources

Wir werden uns dann weiter mit den NP-Problemen beschäftigen!

scattered-lenity