Komplexitätsmaße TIME and SPACE :

specific part of [[theo2_VergleichModelleBerechenbarkeit]] broad part of [[112.00_anchor_overview]]

Bis dato haben wir nur entschieden, ob etwas berechnet / bestimmt werden kann oder nicht. Uns fehlt also noch ein Maß, um irgendwie determinieren zu können, wie lange oder wie viel Platz eine solche TM benötigt –> denn unendlich können sie nur theoretisch sein x)

Wir möchten also definieren: wie schnell oder mit welchem Zeitaufwand wir ein Problem lösen können. Dass es zu lösen ist, steht meist fest. Diese Bestimmung soll dabei unabhängig zur Architektur sein, also ist eine Beschreibung mit Zeit direkt suboptimal.

Zeitkomplexität:

Sei $M$ eine deterministische Einband-Turingmaschine über einem gegebenen Eingabealphabet $\Sigma$, die immer anhält. wie beschreiben wir mit diesem Kontext jetzt Zeitkomplexität? #card Dann beschreiben wir die Zeitkomplexität $Tim{e}_M(x)$ als, die Berechnung von $M$ auf $x$, wobei diese die benötigten Rechenschritte bis zum Anhalten der TM$M$ beschreibt. Also die Zeitkomplexität von M ist eine Funktion $(!)Tim{e}_M:\mathbb{N}⟶\mathbb{N}$ die folgend definiert ist: $Tim{e}_M(n)=maxTim{e}_M(x)|x\in {\Sigma }^{\ast }|x|=n$

Speicherplatzkomplexität:

Se $M$ eine deterministische Einband-Turingmaschine über einem spezifischen Eingabealphabet $\Sigma$, die immer anhält. Sei $C$ eine beliebige Konfiguration von $M$. Die Speicherplatzkomplexität der Berechnung von $M$ auf x, notiert mit $Spac{e}_M(x)$ , ist die maximale Anzahl an nicht-leeren Zellen auf dem Ein-/Ausgabeband während der Berechnung von $M$ auf $x$. Wir beschreiben die Speicherplatzkomplexität von $M$ folgend mit einer Funktion $Spac{e}_M:\mathbb{N}⟶\mathbb{N}$, ferner definiert folgend: $Spac{e}_M(n)=max\{Spac{e}_M(x)|x\in {\Sigma }^{\ast },|x|=n\}$

nicht-leere Zellen:

Wir bezeichnen wir eine Zelle als nicht leere Zelle, sobald die TM einmal auf dieser Zelle operiert hat das heißt, wir müssen sie einfach nur besucht haben. Denn in jedem Rechenschritt muss die TM entweder ein Symbol setzen, oder sich bewegen. Wenn sie sich bewegt, zählt das leere Feld darunter auch als nicht leere Zelle.

[!error] würden wir das nicht betrachten, können wir damit eine Zahl $N$ so codieren, dass man einfach $n$ leere Zellen schreibt und anschließend ein Symbol setzt, was dies anzeigt. Also wir würden theoretisch keinen Speicherplatz benutzen, obwohl wir ihn definitiv brauchen!

Obere/ unter Schranken:

In etwa, wie bei Algorithmen als Schranken definiert [[105.05_algo_onotation#O-Notation / Laufzeitennotationen]].

Sei hier $L$ eine Sprache / alternativ $f$ eine Funktion ( wir können diese Aussage über beides treffen!)

Obere Schranke: Wir sagen jetzt, dass die Funktion $g:\mathbb{N}⟶\mathbb{N},g(n)$ eine obere Schranke für die Zeitkomplexität von $L$ oder auch f ist, falls es eine deterministische TM $M$ gibt, die $L$ entscheiden kann (oder auch f berechnet), so dass dann $Tim{e}_M(n)\in \mathcal{O}(g(n))$ Anders beschrieben heißt dies: $\exists M:Tim{e}_M(n)\in \mathcal{O}$ $\exists M:ma{x}_{|w|=n}Tim{e}_M(w)\in \mathcal{O}$ $\exists M:\exists c>0\forall w:|w|=n:Tim{e}_{M(w)\le }c\cdot g(n)$ relativ wichtig, zum beweisen

Untere Schranke: Wir benennen weiterhin $g(n)$ als eine untere Schranke für die Zeitkomplexität, falls für jede $\forall$ TM $M$, welche $L$ entscheiden kann ( oder f berechnet), gilt, dass $TIM{E}_M(n)\in \Omega (g(n))$ Mit der unteren Schranke beschreiben wir also das absolute Minima, was maximal erreicht werden. Anders beschrieben also: $\forall M:Tim{e}_M(n)\in \Omega (g)$ $\forall M:ma{x}_{|w|=n}Tim{e}_m(w)\in \Omega (g)$ $\forall M:\exists c>0\exists w:|w|:=n:Tim{e}_M(w)\ge c\cdot g(n)$ auch wichtig zum beweisen

alle TMs, die diesen Algo/diiese Sprache/Funktion berechnen können, müssen definitiv so schnell oder langsamer sein. Darunter liegt nichts, und wenn, dann ist das die neue unterste Schranke

Details einer Turingmaschine sind egal:

Im Moment ist unsere Definition nur auf die Komplexität einer Turingmaschine M limitiert. Was machen wir jetzt mit der Betrachtung für die verschiedenen Typen von TMS ( Kellerautomaten, non deterministische etc). Am Ende ist der Aufbau einer TM in dieser Betrachtung beinahe egal. Das wird ersichtlich mit der folgenden Betrachtung:

Behauptung:

Sei $f:\{0,1{\}}^{\ast }⟶\{0,1{\}}^{\ast }$ eine Funktion, die von einer TM $M$ mit einem Arbeitsalphabet $\Sigma$ in Zeit $T(n)$ berechnet werden kann. Dann kann diese Funktion auch von einer TM $\bar{M}$ mit dem Arbeitsalphabet $\{0,1,\square ,\bar{\square }\}$ in Zeit: $\bar{T}(n)=4\log (|\Sigma |)\cdot T(n)$ berechnet werden. Die Idee für den Beweis folgt aus der Idee, dass: Kodiere jeden Buchstaben von $\Sigma$ mit $\log (|\Sigma |)$ vielen binären Bits. Also wir werden mit dieser Operation merken, dass $f\in \mathcal{O}(T(n))⟺f\in \mathcal{O}(\bar{T}(n))$ sein wird.

Selbiges für verfügbaren Speicherplatz: Sei $M$ eine TM mit $k$-Bändern, die die Funktion $f:\{0,1{\}}^{\ast }⟶\{0,1{\}}^{\ast )}$ in einer bestimmten Zeit $T(n)$ berechnet. Dann gibt es auch eine Einband-TM, die diese Funtion in $5\cdot k\cdot T(n{)}^2$ Zeit berechnen kann. Wir wissen dabei aber, dass wir unter einer Betrachtung von $\mathcal{O}$ also der Tendenz von $n$ in Richtung Unendlichkeit diverse Konstanten herausfallen werden und wir so mit selbiger Zeit resultieren.

alle weiteren, anderen Turingmaschinen folgen dann dem gleichen Schema. Das heißt, dass TMs, mit

• anderer Schreibkopf-Bewegung
• verschiedenen Band-Typen (einseitig/beidseitig …) genau gleich sind!

Ausnahme nd-TM:

Es ist ganz sicher nicht egal nicht-deterministische und deterministische Turingmaschinen gleichzustellen. Sie sind sehr wohl unterschiedlich in ihrer Zeit, denn: Die Verwendung einer nicht-deterministischen TM kann die Berechnung exponentiell schneller machen. Umgekehrt haben wir gesehen, dass wir jede nicht-deterministische TM mit einer deterministischen TM simulieren können, jedoch ist es dennoch so, dass sich diese Transformation in der Laufzeit wiederspiegelt! Die Laufzeit kann hierbei exponentiell größer werden!

Komplexitätsklasse $P$:

Komplexitätsklasse $TIME(T(n))$:

Sei $T:\mathbb{N}⟶\mathbb{N}$ eine beliebige Funktion. Wir beschreiben jetzt dei Komplexitätsklasse $TIME(T(n))$ als die Menge aller prachen $L\subset \{0,1{\}}^{\ast }$ die in Worst-Case-Laufzeit $\mathcal{O}(T(n))$ von einer deterministischen TM entschieden werden können: Folglich definieren wir diese Beschreibung so: $TIME(T(n))=\{L\subset \{0,1{\}}^{\ast }|\exists \text{ det TM M, die L entscheidet und }Tim{e}_M(n)\in \mathcal{O}(T(n))\}$ Manchmal wird die Notation auch mit $DTIME(T(n))$ vorgenommen, wobei D für Deterministisch steht!

Komplexitätsklasse $SPACE(S(n))$:

Sei $S:\mathbb{N}⟶\mathbb{N}$ eine Funktion. Die Komplexitätsklasse $SPACE(S(n))$ ist folglich die Menge aller Sprachen $L\subset \{0,1{\}}^{\ast }$ die im Worst Case mit dem Speicherplatzbedarf $\mathcal{O}(S(n))$ von einer deterministischen TM entschieden werden können. Wir definieren diese Beschreibung mit: $SPACE(S(n))=\{L\subset \{0,1{\}}^{\ast }|\exists \text{ det. TM M, die L entscheidet und }Spac{e}_M(n)\in \mathcal{O}(S(n))\}$ Auch hier ist sonst noch die Beschreibung $DSPACE(S(n))$ gültig.

Polynomielle Klassen $P$ und $PSPACE$:

Wir können jetzt die Komplexitätsklasse von $P$ definieren und schreiben sie folgend auf: $P\bigcup _{d\in \mathbb{N}}TIME(n^d)$ , also P enthält alle Sprachen, die in polynomieller Lauzeit von einer deterministischen TM entschieden werden können. Analog gilt dies natürlich auch für die Betrachtung von Speicherplatz: $PSPACE=\bigcup _{d\in \mathbb{N}}SPACE(n^d)$

[!warning] Entscheidungsproblem! Traditionell werden die Komplexitätsklassen für Entscheidungsprobleme über Sprachen definiert - also etwa, dass wir ein Wort $w$ in $L$ haben oder nicht. - aber nicht über Funktionen!

In der Praxis ist es aber üblich, dass man nicht immer Entscheidungsprobleme betrachten - Shortest path, search problems, etcetc.

Unter Umständen kann man aber dennoch Problemtypen zwischen diesen beiden Bereichen hin- und herschieben.

Beispiele dafür bilden etwa:

• Optimierungsprobleme: Finde den kürzesten Weg zwischen $s$ und $t$ –> Ist kein Entscheidungsproblem!
• Entscheidungsprobleme: Gibt es einen Weg zwischen $s$ und $t$ der Länge höchstens $K$ ? –> Ist jetzt eine Ja/Nein Frage,

Komplexitätsklasse $NP$:

Wir konnten jetzt deterministische TMs betrachten und einordnen, etwa unter der Annahme, dass wir mit diesen ein Problem in polynomieller Zeit lösen können. Wir wollen jetzt nicht-deterministische TMs betrachten.

(RE)-Definition von $TIM{E}_N(w)$:

Sei $N$ eine nicht-deterministische TM über dem Eingabealphabet $\{0,1\}$. Für ein beliebiges Wort $w\in \{0,1{\}}^{\ast }$ ist die Zeitkomplexität nun folgend mit : $TIM{E}_N(w)$ beschrieben. Weiter ist die Zeitkomplexität von $N$ auf $w$ die Länge der kürzesten akzeptierenden Berechnungen, die weiterhin $w$ entscheidet - falls es 0 ist, dann haben wir keine akzeptierende Berechnung gefunden.

[!warning ] Scheinbar ähnlich/gleich, wie bei Deterministischen, aber wir betrachten hier nicht, dass wir die kürzeste Berechnung heraussuchen und ausgeben!

Sei ferner $N$ eine nicht-deterministische $TM$ über $\{0,1{\}}^{\ast }$. Dann ist $TIM{E}_N(n)=\max \{TIM{E}_N(w)||w|=n,w\in L(N)\}$ . Falls es kein $w$ gibt, das Länge $n$ hat und in $L$ ist, setzen wir das Ergebnis $TIM{E}_N(n)=0$! Wir haben hier die Definition nur über Wörter über $L(N)$ gesetzt, also ganz anders, als bei det. TMs.

Obere Schranken - schwach /stark beschränkt:

Sei $t:\mathbb{N}⟶\mathbb{N}$ eine Funktion. Wir sagen jetzt, dass eine nicht det. TM $N$ schwach-t(n)-bschränkt ist, falls für alle $n\in \mathbb{N}$ gilt: $TIM{E}_N(n)\in \mathcal{O}(t(n))$.

Ferner ist N stark-t(n)-beschränkt, wenn jede( immernoch nur akzeptiert!) Berechnung auf w höchstens $t(|w|)$ Schritte macht!

Komplexitätsklasse $NTIME(T(n))$:

Sei $T:\mathbb{N}⟶\mathbb{N}$ . Die Komplexitätsklasse $NTIME(T(n))$ ist nun die Menge aller Sprachen $L\subset \{0,1{\}}^{\ast }$ die in Worst-Case-Laufzeit $T(n)$ von einer nicht-det TM akzeptiert werden können. Das heißt jetzt: $NTIME(T(n))=\{L\in \{0,1{\}}^{\ast }|\exists \text{ nicht det TM mit }L(N)=L\wedge Tim{e}_N(n)\in \mathcal{O}(T(n))\}$ und außerdem: $⟺\{L\in \{0,1{\}}^{\ast }|\exists \text{ nicht det. TM N, die schwach-tn-beschra¨nkt ist, mit }L(N)=L\}$

Komplexitätsklasse $NP$:

Wir definieren jetzt die Komplexitätsklasse $NP$ wie folgt: $NP=\bigcup _{d\in \mathbb{N}}NTIME(n^d)$ - also wir haben nicht det TMs, die diese Berechnung in polynomieller Zeit hinbekommen! $NP$ = Nicht-det, polynomielle Zeit

NTMs gibt es nicht wirklich :

x)

• irgendwie klar, aber um es nochmal deutlich anzumerken: NTMS sind nur ein theoretisches Konstrukt
• Es ist erstaunlich hilfreich dabei, relevante echte Dinge zu charakterisieren - wie schwer ein Problem theoretisch ist.
• Aber natürlich kann man so etwas nicht bauen
  • Quantencomputer kommen dem nur nahe, können aber auch nicht komplett nicht-det agieren!

Diese Komplexitätsklassen können wir jetzt in diversen Beispielen betrachten und damit Probleme kategorisieren.

Angewandte Komplexitätsklassen:

Boolesche Formeln:

Eine boolesche Forme - log. Forme - besteht aus booleschen true/false Variablen / Literalen (TI), die durch die Operatoren :

1. $\wedge$ Konjunktion
2. $\vee$ Disjunktion
3. $\neg$ Negation verknüpft werden.

Dieses Problem finden wir besipielsweise in der Anwendung von DNF/KNF in der technischen Informatik 1.

Erfüllbare Formel :

Eine boolesche Formel nennen wir jetzt erfüllbar, wenn es eine Belegung der Variablen mit Werten (True/False) gibt, sodass unsere Formel wahr ist. Also etwa eine Formel, wie $x_1\wedge x_2\wedge x_3$

Klauseln:

Eine Klausel definieren wir folgend eine Formel, die nur aus Disjunktionen zwischen Literalen/Variablen besteht. Wir nennen diese Struktur dann eine konjunktive Normalform, wenn wir ein viele Klauseln konjunktiv zusammenschließen können: $Klause{l}_1\wedge Klause{l}_2\dots$

Behauptung : $\forall$ Bool. Funktion $\exists$ CNF:

Jede beliebige Boolesche Funktion kann durch eine CNF-Formal ausgedrückt werden - exponentielle Länge, denn wir haben $l^2$ Belegungen bei $l$ Belegungen.

[!Behauptung] Sei $f:\{0,1{\}}^{\ast }⟶\{0,1\}$ eine beliebige Funktion. Dann gibt es eine boolesche Formel $\mu$ in CNF mit $l$ Variablen und einer Länge von $\le l\cdot 2^l$, so dass für alle $u\in \{0,1{\}}^l"\mu (n)=f(n)"$ Die Länge einer boolschen Formel steht hier für die Anzahl der $\wedge \vee$ Zeichen in der Formel

Um dies zu beweisen betrachten wir eine passende Konstruktion:

Beweis:

Betrachten wir ein beliebiges Wort $v\in \{0,1{\}}^l$. Wir möchten ferner eine Klausel $c_v$ mit genau $l$-Variablen konstruieren. Die Variablen werden passend beschrieben mit : $z_1,\dots ,z_l$, sodass wir dann gelten lassen können: $c_v(u)=\left(\begin{array}{cc}1& \text{ falls }u\ne v\\ 0& \text{ falls }u=v\end{array}\right)$ Also wir entscheiden einfach für eine beliebige Eingabe und mappen dies dann entweder mit 1 oder 0. Für $v=(v_1,\dots ,v_2)$ wählen wir jetzt die passende Klausel $c_v=(a_1\vee a_2\vee \dots \vee a_l)$ mit folgender Struktur: $a_i=\left(\begin{array}{cc}{z}_1& \text{ falls}{v}_i=0\\ {\bar{z}}_1& \text{ falls}{v}_1=1\end{array}\right)$

Wir möchten jetzt diese gegebene Klausel in einer CNF zusammenfassen, die das Problem lösen wird:

Sei $v:=\{v\in \{0,1{\}}^l|f(v)=0\}$. Wir möchten jetzt die Formel: $\mu =\underset{v\in V}{\bigwedge }{c}_v$ Durch unsere Konstruktion gilt jetzt weiterhin: $\mu$ ist in CNF $\mu (z)=0⟺f(z)=0$ Die Länge von $u$ ist $\le l\cdot 2^l$ denn:

• jedes $c_v$ hat die Länge $l-1$ ( l gibt die Menge der Operatoren an)
• $|V|\le 2^l$

Aufbauen zu dieser Entscheidung möchten wir jetzt das SAT Problem nohcmals definieren, auch schon hier [[111.99_algo_ProblemComplexity#Unsolvable Problems]]

SAT - Satisfiability Problem :

Gegeben sei eine boolesche Formel in einer konjunktiven Normalform. Es besteht die Frage, ob diese Formel erfüllbar ist, also wir eine Belegung der Variablen finden können, sodass die Formel wahr ist.

Dies können wir beweisen, indem wir eine SAT-Formel mit $n$ Literalen über $m<n$ Variablen gegeben betrachten und jetzt eine beliebige / zufällige Belegung betrachten. Da wir etwas non-deterministisches haben, kann die konstruierte Maschine diese zufälligen Belegungen schnell berechnen und die Antwort in polynomieller Zeit finden.

Von SAT gibt es noch weitere Variationen, wie etwa 3-SAT, K-Sat, wobei die Variable K einfach angibt, wie viele unbekannte in jeder CNF auftaucht!

Polynomzeit-Reduktion