date-created: 2024-07-02 12:18:54 date-modified: 2024-09-27 03:04:44

Probleme | P | NP

anchored to 112.00_anchor_overview

proceeds from 112.22_komplexitaets_klassen

Overview

Wir wollen ferner diverse Beispiele und Probleme betrachten, die wir als $P$ - schwer - also in polynomieller Zeit lösbar - beschreiben können.

Bedenke, dass

PATH | Pfade s -> t

[!Req]

Sei $G=(V,E)$ ein gerichteter Graph, definiert durch eine Matrix $G_{ij},G_{ij}=1$ gdw. es eine Kante von Knoten $i\to j$ gibt.

Wir setzen jetzt folgende Sprache: $$PATH=\{⟨G,s,t⟩\mid G\text{ ist ein gerichteter Graph mit Pfad }s\to t\}$$

Es gilt dabei dann $PATH\in P$

Warum, wie können wir das beweisen? Was gilt für solche algorithmischen Probleme meist? #card

Wir können das unter Konstruktion des Algorithmus beweisen!

Der Algorithmus is offensichtlich in $DTIME(n^2)\subset P$ und somit ist es $\in P$!

\begin{algorithm} 
\begin{algorithmic} 
\Procedure{M}{G,s,t}
\State $V = [s]$  \Comment{ markiere s, $\mathcal{O}(1)$}
\State $T = 0$
\While{$T \neq 0$} \Comment{höchstens n mal durchlaufen, alle Knoten also} 
  \State $T=1$ 
  \For{$v \in V$} 
  \State \Comment{höchstens n, alle markierten Knoten}
  	\If{ $v \text{ hat Nachfolger }k$}
  		\State $V = [V,k]$
  		\State $T = 0$ \Comment{damit wird Loop beendet!}
  	\EndIf
  
  \EndFor 
\EndWhile
\If{$t \in V$} 
\State $accept$
\Else \State $reject$ 
\EndIf 

\EndProcedure
\end{algorithmic}
\end{algorithm}

Generell:

• Betrachten wir ein Problem, welches man Algorithmisch beschrieben oder zeigen kann
• möchten wir jetzt die Komplexität des Problemes finden / bestimmen können, so können wir hier einfach den Algorithmus explizit angeben und dann direkt zeigen, dass $\in P$ etc.

Kontextfreie Grammatiken | $w\in L$?

requires knowledge about: 112.08_grammatiken

[!Definition]

Sei $L$ eine $CFL$, die vom $CFGG$ in Chomsky Normalform erzeugt wird.

Wie können wir bestimmen, ob $w\in L$ liegt, also ein Wort der Grammatik entspricht? #card

Beweis Wir bauen den Entscheider $D$ für $L$ auf $w$ mit $\mid w\mid =n$ mit Hilfe von dynamic programming

Dafür füllen wir eine obere Dreiecksmatrix $T$ mit $\frac{1}{2}n(n+1)$ Einträgen, sodass $T_{ij}$ alle Variablen enthält, die dann $w_i,w_{i+1},\dots ,w_j$ generieren kann

Dabei ist jedes Element von $T$ eine endliche Liste!

Betrachtung | Nicht-Deterministische-Turing-Maschinen

Wir wollen uns jetzt 112.13_turing_maschinen_nondeterministisch anschauen und folgend die Komplexität bzw. deren Zeit- und Speicheraufwand betrachten!

[!Definition]

Sei $N$ eine nicht-deterministische TM über einem Eingabealphabet $\Sigma =\{0,1\}$.

Für ein Wort $w\in \{0,1{\}}^{\ast }$ ist dann die Zeitkomplexität folgend beschrieben:

Wie können wir die Zeitkomplexität beschreiben, was ist die Limitation hier? #card

Wir wissen ja, dass eine NDTM in ihrer Ausführung einen Baum etabliert, wo viele verschiedene Ausrechnungspfade auftreten, wobei wir die übernehmen, wo unsere DNTM garantiert akzeptiert! Das ist dann ein valider Pfad, den wir betrachten wollen.

Ferner müssen wir für die Zeitkomplexität also alle dieser Pfade betrachten und werden ferne bestimmte herausnehmen / betrachten: $$Tim{e}_N(n)=\max \{Tim{e}_N(w)\mid w\mid =n,w\in L(N)\}$$

also wir suchen die kürzeste Berechnung für eine konkrete Eingabe $w$!

Falls es kein $w$ von Länge $n$ in L gibt, setzen wir $Tim{e}_N(n)=0$

Diese Definition ist dann also nur über Wörter $\in L(n)$, anders als bei deterministischen TMs.

Aus diesem Grund brauchen wir auch noch weitere Definitionen.

[!Feedback] Definition | beschränkte NTM

Sei $t:\mathbb{N}\to \mathbb{N}$ eine Funktion.

Wann sprechen wir von einer $t(n)$ beschränkten NTM ? #card

Wir sagen, eine NTM $N$ ist $t(n)$ beschränkt, falls $$Tim{e}_N(n)\in \mathcal{O}(t(n)),\forall n\in \mathbb{N}$$

Komplexitätsklasse | Zeitkomplexität

Ferner können wir dann die Komplexitätsklasse für diese Laufzeiten beschreiben:

[!Beweis] Definition $NTIME$

Sei jetzt $T:\mathbb{N}\to \mathbb{N}$.

Wir beschreiben die Komplexitätsklasse $NTIME(T(n))$ folgend.

was muss für eine Sprache L gelten, damit sie in der Klasse ist ? Wie beschreiben wir dei Sprache dann richtig? #card

Wir beschreibe damit die Menge aller Sprachen $L\subseteq \{0,1{\}}^{\ast }$, die in worst-case Laufzeit $T(n)$ von einer nicht-deterministischen TM akzeptiert werden können.

Beschrieben wird das etwa mit : $$NTIME(T(n))=\{L\in \{0,1{\}}^{\ast }\mid \exists \text{ nicht-det }TMN\text{ mit }L(N)=L\wedge Tim{e}_N(n)\in \mathcal{O}(T(n))\}$$

Komplexitätsklasse | Speicherkomplexität

Wir können jetzt auch eine Komplexitätsklasse für die Speicherkomplexitäten von Sprachen beschreiben.

Wir gehen dabei analog zu der Definition der Zeitkomplexität, also NTIME, vor:

[!Beweis] Definition | $NSPACE$

Wir wollen dafür zuerst für eine bestimmte NDTM $N$ die Klasse $Spac{e}_N(w)$ definieren, welche also den Speicherplatz derjenigen akzeptierenden Berechnungen von $N$ auf $w$ zusammenfässt. Ferner können wir damit dann auch die Komplexitätsklasse $NSPACE$ beschreiben.

Wie definieren wir dann $Spac{e}_N$ und ferner die Klasse $NSPACE$? #card

Wir beschreiben den benötigten Speicherplatz einer Berechnung auf $N$ für $w$ folgend: $$Spac{e}_N(n)=\max \{Spac{e}_N(w)\mid \mid w\mid =n,w\in L(N)\}$$

und ferner die Komplexitätsklasse: $$NSPACE(s(n))=\{L\in \{0,1{\}}^{\ast }\mid \exists NDTMN\text{ mit }L(N)=L\wedge Spac{e}_N(n)\in \mathcal{O}(s(n))\}$$

Komplexitätsklasse | NP

Aus der obigen Definition können wir dann jetzt die Komplexitätsklasse NP definieren!

[!Korollar] Definition NP-Probleme

Wir wollen also Sprachen definieren, die in polynomielle Zeit von einer nicht-deterministischen TM entschieden werden können.

Wie beschreiben wir die Menge $NP$ ? #card

$$NP:=\bigcup _{k\in \mathbb{N}}NTIME(n^k)$$

–> Das heißt als, dass $NP$ alle Sprachen enthält, die in polyonomieller Laufzeit von einer nicht-det Turingmaschine entschieden werden können!

NP steht also nicht für nicht polynomiell, sondern nicht-deterministisch polynomiell

Beispiel | Clique Problem

Problem wurde schon in folgenden Bereichen definiert und besprochen:

• 111.99_algo_ProblemComplexity
• 111.99_algo_approximationAlgorithms
• 115.09_Graphen_Knotenfärbung

[!Beweis] Definition

Sei $G=(V,E)$ ein ungerichteter Graph. Eine Clique ist jetzt ein Subgraph von $G$, wenn alle Knoten paarweise miteinander verbunden sind. Das heißt er ist vollständig!.

Wie können wir jetzt das Clique-Problem beschreiben? #card

Das Clique-Problem ist dann die Entscheidung, ob ein Graph $G=(V,E)$ mit $n$ Knoten eine Clique von Größe $k\le n$ enthält!

Es beschreibt also folgende Menge: $$CLIQUE=\{⟨G,k⟩\mid G\text{ ist ein Graph mit einer k-Clique}\}$$

Hierbei besteht jetzt das Theorem, dass $CLIQUE\in NP$ ist!

Beweis | Clique-Problem ist NP-hard

Wir möchten folgend beweisen, dass es NP-hard ist und das wiederum dann als eine allgemeine Erkenntnis definieren, die für andere Probleme wichtig ist!

[!Bsp] Beweis

Wir nehmen an, dass $CLIQUE\in NP$

Wir möchten das jetzt folgend beweisen:

Welche drei Schritte benötigen wir und was ist der Schritt der Verifikation? #card

Wir konstruieren jetzt eine NTM $N$ , welche die Eingabe $⟨G,k⟩$ erhält ( Was ein entsprechender Graph und die gewünschte Größe der Clique $k$ ist)

Wir gehen wie folgt vor:

1. wähle nichtdeterministisch einen Satz $c_j$ von $k$ Knoten aus V (also random Knoten!) –> das liegt in $\mathcal{O}(1)$
2. teste jetzt ob $E$ alle Kanten enthält, die Knoten in $c_j$ verbinden (also wir wollen schauen, dass wir hiermit einen vollständigen Graphen erwischt haben!) –> das liegt in $\mathcal{O}(k^2)(k\le n)$
3. falls wir das gefunden haben (ist es eine Lösung) $accept$, sonst reject –> das ist auch $\mathcal{O}(1)$

Da wir jetzt nichtdeterministisch einfach parallel alle solche Kombinationen versuchen, werden wir garantiert eine Lösung finden, wenn sie denn überhaupt existiert!

Unter Anwendung der Verifikation | können wir dann jetzt beweisen, dass man polynomiell durch die Antworten der NTM gehen kann, um ein einzelnes $c_i$ (Also ein Pfad, der aufgemacht wurde) zu verifizieren –> schauen, ob es eine Clique ist oder nicht!

Also wir haben in zwei Teile aufgeteilt

1. Eine NTM, die nichtdeterministisch Vorschläge generiert –> hier sucht sie einfach gleichzeitig verschiedene Knotenpaare aus, die geprüft werden müssten
2. Ein deterministischer Algorithmus, von polynomieller Laufzeit um dann einen expliziten Vorschlag $c_j$ zu zertifizieren –> zu prüfen, ob er es löst oder nicht

Verifikation | Verifizier

So, wie obig beschrieben, kann man jedes NP-schwere Problem aufteilen!

[!Definition] Verifizierer

Unser Beispiel gibt an, dass man ein solches Problem aufteilen kann in:

• eine NTM, die die Vorschläge liefert (nicht deterministisch, also parallel!)
• einen Verifizierer, der anschließend die Vorschläge auswerten und eindeutig eine Antwort geben kann.

Wir möchten unter dieser Vorbetrachtung jetzt einen Verifizierer definieren und diesen als alternative Charakterisierung von NP-Problemen beschreiben.

Wie ist der Verifizierer Definiert? Es müssen zwei Schritte gelten, welche? #card

Wir betrachten jetzt eine Funktion $p:\mathbb{N}\to \mathbb{N}$.

Wir nennen eine DTM (deterministisch wohlgemerkt!) $M$ jetzt $p-$Verifizierer für eine Sprache $L\subset \{0,1{\}}^{\ast }$ wenn folgendes gilt:

1. Für alle $w\in L$ gibt es einen String $c\in \{0,1{\}}^{\ast }$ - was wir Zertifikat nennen! - mit $\mid c|\le p(\mid w\mid )$, sodass $M$ bei der Eingabe von $w,c$ akzeptieren wird.
2. Falls $w\notin L$, dann gilt für alle $c\in \{0,1{\}}^{\ast }$, dass $M$ bei Eingabe von $w,c$ nach höchstens $p(\mid w\mid )$ Schritten stoppt und dann verwirft (das hier nicht zwingend “zu Ende” berechnet wird, ist nicht weiter ein Problem, weil wir damit die Aussage nicht falsifizieren)

Wenn jetzt $p$ ein Polynom ist, dann ist $M$ ein Verifizierer in polynomieller Zeit! und die Sprache $L$ heißt polynomiell verifizierbar.

Die entscheidende Eigenschaft des Verifizierers ist, dass dieser deterministisch ist!

Beispiele für Verifizierer

Wir möchten folgend ein paar Verifizierer anschauen:

[!Tip] Auswahl an Verifizierer

nenne drei verifizierer #card

Wir kennen schon den CLIQUE Verifizierer Beweis | Clique-Problem ist NP-hard

Independent-Set:

Gegeben sei ein Graph $G$ mit $n$ Knoten und $k\le n$.

Gibt es eine unabhängige Knotenmenge der Größe $k$ - d.h. eine Menge, sodass es paarweise keine direkten Kanten zwischen ihren Elementen gibt?

–> Wir können einen Verifizierer beschreiben

Verifizier: Gegeben eine Knotenmenge können wir offensichtlich in $\mathcal{O}(k^2)$ verifizieren, dass alle $k^2$ Paare keine Kanten teilen!

Traveling Salesman:

Gegeben sei ein gewichteter Graph, $c>0$, gibt es eine Route durch alle Knoten des Graphen von Länge $\le c$?

–> Auch das können wir verifizieren

Verifizierer: Gegeben einer Route können wir natürlich in $\mathcal{O}(n)$ diese Route durchlaufen und ihre Länge berechnen und dann begründen, ob $\le c$ oder nicht!

Verifizierbarkeit $⟺$ NP-Berechenbarkeit

[!Satz]

Es gilt jetzt: $L\in NP⟺L\text{ ist polynomiell verifizierbar}$

Wie kann man das in etwa beweisen? #card

Wir müssen hierbei natürlich beide Richtungen beweisen:

1. $⟹$ Sei $L\in NP$, das heißt es gibt eine NTM $N$ mit $L(N)=L$ und $TIM{E}_N(n)=p(n)$ für ein Polynom $p$.

• Wir können jetzt alle Berechnungspfade von $N$ in einem Baum von tiefe $\mathcal{O}(p(\mid w\mid ))$ aufschreiben –> der Baum könnte etwa binär sein ( O.b.d.A)
  • Die Knotenzahl ist durch $\mid konfiguration|$ beschränkt und ${\log }_{b}x={\log }_2(x)/{\log }_2(b)\approx {\log }_2(x)$
• Ein Pfad durch den Baum kann also durch einen binären String $c$ beschrieben werden –> der an jedem Knoten sagt, welche Abzweigung genommen wird, um diesen zu traversieren
• Falls das Eingabewort $w\in L$ ist, dann gibt es also einen Pfad von Länge höchstens $\mathcal{O}((p(w)))$, der in einem akzeptierenden Zustand endet. –> Sei dann $c_w$ der String, der diesen Pfad beschreibt
• Wir müssen zeigen, dass $c_W$ ein Zertifikat ist!

Das machen wir folgend:

• Der Verifizierer $V$ bekommt jetzt $⟨w,c_w⟩$ als Eingabe.
  • Er simuliert den Berechnungspfad von $N$. Dass diese Berechnung deterministisch ist, folgt, da $c_w$ den deterministischen Pfad identifiziert –> wir haben es so gebildet, dass er genau diesen ausgibt / bzw “beschreibt / findet”
  • Die Berechnung des Verifizierers $V$ endet daher nach $p(\mid w\mid )$ Schritten in einem akzeptierenden Zustand –> weil $c_w$ die Länge aufweist / beschreibt!
  • Wenn dann das Zertifikat abgeschritten wurde - auch nach $\mathcal{O}(p(\mid w\mid ))$ Schritten - und weiter kein akzeptierender Zustand erreicht wurde, dann darf $V$ abbrechen und mit $reject$ ablehnen –> das darf er, weil wir durch die Konstruktion von $c_w$ wissen, dass dieser einen passenden Pfad im Baum darstellt / beschreibt.

2. Rückrichtung $\Leftarrow$ Sei $V$ ein Verifizierr in polynomieller Zeit für $L$.

Dann müssen wir jetzt eine NTM $N$ konstruieren, die $w$ akzeptiert, falls $w\in L$ (Also die eine Eingabe prüft / testet)

Das machen wir folgend:

• $N$ probiert einfach nicht-deterministisch alle potentiellen Zertifikate für $V$ durch –> diese sind alle Strings $c$ von endlicher Länge $\in \mathcal{O}(P(\mid w\mid ))$ - und davon gibt es nur endlich viele!
• Falls jetzt $w\in L$, dann gibt es per Definition von L ein $c$, sodass $V$ mit Eingabe $⟨w,c⟩$ akzeptiert! –> Das ist dann auch ein akzeptierender Berechnungspfad von $N$!
• Falls $w\notin L$, dann gibt es keinen akzeptierenden Pfad und somit $N$ –> auch nicht akzeptierend!

Damit haben wir beide Seiten abgedeckt und entsprechend bewiesen!

$P,NP,EXP$ | Relationen

[!Definition]

Es gilt $P\subseteq NP\subseteq EXP$ Hierbei ist $$EXP:=\bigcup _{c>1}DTIME(2^{n^c})$$

Wie könnten wir das beweisen? #card

Wir wollen dafür jede Etappe einzeln beweisen:

1. $P\subseteq NP$ gilt nach dem eben bewiesenen Satz Verifikation | Verifizier –> weil hier die polynomielle Berechnung in $P$ selbst auch ein Zertifikat ist und wir es somit übernehmen können!
2. $NP\subseteq EXP$. Sei jetzt $L\in NP$. Dann können wir alle möglichen Verifizierer - also alle Pfade der NTM - in $2^{\mathcal{O}(p(n))}$ aufzählen. Da $p(n)$ ein Polynom ist, gilt dann auch $$p(n)\in \mathcal{O}(n^c)$$ für ein $c>1$ und somit dann halt auch $$2^{\mathcal{O}(p(n))}=2^{n^c}$$

NP steht also nicht für “nicht polynomiell”, aber durchaus für höchstens exponentiell –> also wir haben einen Upperbound gefunden!

Philosophische Bedeutung von NP

Oberflächlich betrachtet geht es hier bei der Frage von $P\ne NP$ um den Unterschied zwischen Nicht-Determinismus und Determinismus (wie auch schon zuvor!). Aber die Verbindung zu Verifizierern gibt ihr noch ein philosophisches Gewicht

Denn:

[!Attention]

• Wenn $P=NP$, dann wäre das erfinden von Beweisen und deren Prüfung gleich schwer

ABER was wir aus der Realität wissen:

• Die Schönheit einer Bachkantate zu erkennen ist einfacher als sie zu verbessern, bzw.
• Die Statik einer Brücke zu prüfen ist einfacher als ihre Konstruktion zu erfinden!

Oder wie es auch in einem Brief von Kurt Gödel Gödelisierung an John von Neumann (RAM-Architektur) formuliert wurde:

Wenn es wirklich eine Maschine mit $\phi (n)\sim k\cdot n$ (oder auch nur $\sim k\cdot n2$) gäbe, hätte das Folgerungen von der grössten Tragweite. Es würde nämlich offenbar bedeuten, dass man trotz der Unlösbarkeit des Entscheidungsproblems die Denkarbeit des Mathematikers bei ja-oder-nein Fragen vollständig durch Maschinen ersetzen könnte. Man müsste ja bloss das n so gross wählen, dass, wenn die Maschine kein Resultat liefert, es auch keinen Sinn hat über das Problem nachzudenken. Nun scheint es mir aber durchaus im Bereich der Möglichkeit zu liegen, dass $\phi (n)$ so langsam wächst.

Tool | Platzkonstruierbare Funktionen

Betrachten wir nochmals die zuvor definierten Klassen $P$ und $NP$:

Ferner möchten wir jetzt darauf schließen (können), dass etwa $TIME\subset SPACE$

Dafür möchten wir eine Struktur - spezifischer Funktion - einfuhren, die eine bestimmte Menge von Speicher garantiert nutzen wird!

[!Req] Platzkonstruierbare Funktionen

Wir wollen ferner eine Funktion $s:\mathbb{N}\to \mathbb{N}$ als platzkonstruierbar bezeichnen, wenn wir sie folgend beschreiben bzw. sie folgend berechnen kann:

Was für eine TM müssen wir konstruieren können? Welche zwei Eigenschaften müssen im Bezug zur Funktion $s(n)$ gelten? #card

Wir nennen eine solche Funktion folgend platzkonstruierbar, wenn es eine DTM - deterministisch! - gibt, die $s(\mid x\mid )$ in der Speicherkomplexität $\mathcal{O}((s ( \midx \mid )))$ berechnen kann.

Präziser heißt das:

• wir haben eine $1$-Band TM $M$ mit einem separaten - read only

Und damit können wir zwei Folgerungen dazu aufstellen:

1. $Spac{e}_M(n)\le s(n)$ für alle $n\in \mathbb{N}$
2. für jede Eingabe $0^n,n\in \mathbb{N}$ generiert $M$ das Wort $O^{s(n)}$ auf seinem Arbeitsband und hält in $q_{accept}$ –> Also wir können hier einfach garantieren, dass eine gewisse Menge von Speicher erzeugt / aufweist!

Dabei sind die üblichen monotonen Funktionen, wie etwa ${\log }_2,,n,2^n$ etc sind alle platzkonstruierbar!

Tool | Zeitkonstruierbare Funktionen

Selbige Struktur bzw. Funktion, wie bei der platzkonstruierbaren Funktion möchten wir jetzt auch für die Zeit definieren.

[!Definition] Zeitkonstruierbare Funktionen

Auch hier wollen wir jetzt eine Funktion $f:\mathbb{N}\to \mathbb{N}$ beschreiben, die als zeitkonstruierbar beschrieben wird, wenn sie folgende Eigenschaften aufweist.

was muss für diese Funktion gelten? #card

Auch hier setzen wir die gleichen Strukturen, wie bei der platzkonstruierbaren Funktion um, also :

1. $Tim{e}_M(n)\le f(n)$ $\forall n\in \mathbb{N}$!
2. Die Generation einer Ausgabe ist gleich, zur Tool | Zeitkonstruierbare Funktionen

Ferner gilt jetzt: Die Funktion $x\mapsto f(\mid x\mid )$ hat die Zeit-Komplexität $\mathcal{O}(9f(\mid x\mid ))$

$TIME\subseteq SPACE$

Wir können aus der obigen Konstruktion folgern, dass diese Komplexitätsklasse garantiert eine Teilmenge von $SPACE$ sein muss.

[!Req]

Eine $TM$ kann in $t$ Schritten höchtenns $f$ Bandzellen beschriften.

Es gilt jetzt für eine Funktion: $$t:\mathbb{N}\to {\mathbb{R}}^{+}:TIME(t(n))\subseteq SPACE(t(n))$$

Warum gilt das, was können wir daraus folgern? #card

Wir können jetzt aussagen, dass jede DTM - deterministisch! - $M$ die in der Zeit $Tim{e}_M(n)$ arbeitet, nicht mehr also $Tim{e}_M(n)$ Felder beschreiben kann.

Dadurch gilt also $Spac{e}_M(n)\subseteq Tim{e}_M(n)$ für jede DTM $M$!

Ferner folgt daraus noch ein Korollar:

[!Korollar]

$P\subseteq PSPACE$

Was sagt uns das aus? #card

Wir erhalten hier jetzt also einen upper-bound für die Klasse $P$, weil jedes Problem in der Klasse $PSPACE$ liegt

–> Somit erhalten wir einen upper-bound für den Speicherplatz bedarf

$SPACE\subseteq \exp (TIME)$

[!Satz] Satz

Für jede platzkonstruierbare Funktion $s$ mit $s(n)\ge {\log }_{2}n$ gilt folgend: $$SPACE(s(n))\subseteq \bigcup _{c\in \mathbb{N}}TIME(c^{s(n))}$$

Was können wir damit aussagen, wie können wir das etwa beweisen? #card

Die Speicheraufwände für eine spezifische Funktion $s(n)$ bildet hier also eine untere Schranke, weil sie garantiert eine Teilmenge der Zeitkomplexität ist.

Ferner ist die Speicherkomplexität für $s(n)$ dann eine echte Teilmenge der Zeitkomplexität welche hier polynomiell für eine Konstante $c$ konstruiert ist.

Beweisidee:

Man kann hier ähnlich zum 112.07_pumping_lemma eine Konstruktion aufbauen:

• eine TM die einen beschränkten Bereich des Bandes beschreibt, kann nur durch endlich viele Konfigurationen gehen, bevor sie dann (nachweislich) in einer Schleife ist ( und somit eine Redundanz von Schritten auftritt, die man dann einfach entfernen kann!)

Das kommt daher, dass wir hier keinen “neuen Inhalt” speichern / erzeugen müssen!

Hieraus können wir unsere vorherige Betrachtung der Mengen-Verhältnisse erweitern:

[!Korollar]

$$DLOGSPACE\subseteq P\subseteq PSPACE\subseteq EXPTIME$$

was beschreiben wir mit “DLOGSPACE” und “DEXPTIME” ? #card

• $DLOGSPACE=SPACE({\log }_{2}n)$
• $DEXPTIME={\bigcup }_{c\in \mathbb{N}}TIME(2^{n^c})$

Nichtdeterminismus, bringt höchstens exponentielles Speed-Up

Damit möchten wir vor Allem die Aussage aus [$P,NP,EXP$ | Relationen](#$P,$%20Relationen) erweitern bzw. präzisieren!

[!Satz]

Es gilt jetzt:

Für jede Sprache $L\in NP$ gibt es ein Polynom $p(n)$, und auch eine deterministische TM $M$, sodass $M$ die Sprache $L$ in Zeit $2^{p(n)}$ akzeptier!. Es gilt damit also: $$NP\subseteq DEXPTIME$$

Betrachten wir also eine DTM, die diese Sprache beschreibt, wie kann man sie jetzt in eine NTM übersetzen? #card

Wir versuchen hier also eine ähnliche Aussage, wie bei der Berechenbarkeit zu tätigen.

Man kann den Berechnungsbaum der NTM auch deterministisch nacheinander ablaufen und damit deterministisch genau das gleiche berechnen!

Da dieser Baum exponentiell viele Pfade hat, dauert es dann auch exponentiell länger!

Folgend also formalisiert:

• Sei $L\in NP$ , dann gibt es eine NTM $N$ und ein Polynom $q(n)$, sodass dann $N$ die Sprache $L$ in Zeit $q(n)$ erkennt / erkennen kann.
• Betrachte dabei dann den Berechnungsbaum von $N$. Der Verzweigungsgrad an jedem Knoten ist dann höchstens $$d=\underset{\text{ Bewegung des Schreibkopfes}}{\underbrace{3}}\cdot \underset{\text{ gelesener Buchstabe}}{\underbrace{\mid Q\mid }}\cdot \underset{\text{ na¨chster Zustand}}{\underbrace{\mid \Gamma \mid }}$$
• und aus dieser Struktur betrachten wir alle Pfade bis Länge $q(n)$. Es gibt somit also höchstens $d^{q(n)}$ Pfade!

Wir können diese dann nacheinander ausführen, wann dann folgende Zeit verbrauchen wird: $$d^{q(n)}\cdot q(n)=2^{q(n)\cdot {\log }_{2}d+{\log }_{2}q(n)}\in 2^{\mathcal{O}}((p(n)))$$

$TIME/SPACE$ Für NTM nicht-deterministische

[!Lemma]

Aus den Konstruktionen können wir jetzt ferner noch eine Aussage über alle Funktionen $t,s:s\ge {\log }_{2}n$ treffen.

Welche zwei Aussagen gelten hierbei für die Komplexitätsklassen NTIME und NSPACE ? #card

für diese beide Klassen gilt für diese Funktion folgend:

1. $NTIME(t)\subseteq NSPACE(t)$
2. und auch $NSPACE(s)\subseteq {\bigcup }_{c\in \mathbb{N}}NTIME(c^{s(n)})$

Ein Beweis wäre hier ähnlich / analog zu Nichtdeterminismus, bringt höchstens exponentielles Speed-Up

Aber wir können aus dieser Struktur ferner eine Folgerung ziehen!

[!Satz]

Es gilt für jede platzkonstruierbare Funktion $s$ mit $s(n)\ge {\log }_{2}n$ unter Betrachtung des Lemmas und somit der Einschränkung dass:

1. $NTIME(t)\subseteq NSPACE(t)$
2. und auch $NSPACE(s)\subseteq {\bigcup }_{c\in \mathbb{N}}NTIME(c^{s(n)})$

Jetzt folgendes:

was folgt für diese Betrachtung genauer? #card

Es gilt: $$NSPACE(s(n))\subseteq \bigcup _{c\in \mathbb{N}}DTIME(c^{s(n)})$$

Ein Beweis dafür wird ähnlich geführt, wie die obigen –> indem wir also die Pfade betrachten und dann zusammensetzen. Jedoch ist zu beachten, dass eine NTM, wenn sie in eine bereits zuvor erreichte Konfiguration zurückkehrt, auch anders abzweigen kann.

–> Das kann sie aber nur exponentiell oft (da wir nur so viele Pfade haben!), denn sonst geht sie wieder in eine Schleife uber!

(ausführlicher findet man es in Hromkovič, Satz 6.6.)

Und auch hier können wir unsere Kette an Abhängigkeiten der Komplexitätsklassen erweitern / verlängern:

[!Bsp] Korollar

Wir haben jetzt noch NPSPACE in die Betrachtung eingebracht.

Wir wollen also folgende Klassen ordnen: $$DEXPTIME,P,NPSPACE,NLOGSPACE$$

wo verorten wir sie, wie wird die Relation weiter aufgeschrieben? #card

Es folgt also: $$NLOGSPACE\subseteq P,\wedge NPSPACE\subseteq DEXPTIME$$

Satz von Savitch (Savage)

source can be found here

[!Req] Satz von Savitch

Sei jetzt $s$ mit $s(n)\ge {\log }_{2}n$ eine platzkonstruierbare Funktion. Dann gilt folgendes:

Was gilt jetzt im Bezug auf Space / Nspace? Wie könnten wir das beweisen? #card

Es gilt somit dann: $$NSPACE(s(n))\subseteq SPACE(s(n{)}^2)$$

Ein Beweis könnte man technisch umsetzen. Hierbei schaut man den Graph der möglichen Konfigurationsverläufe an und kann daraus dann die Limitierung des Speicherplatzes etc. evaluieren.

Speicherkomplexität ist gar nicht soo schwer!

Es ist also bekannt, dass $NP=P$ im Bezug auf Speicher

(man kann also gut verstehen, wie gut etwas Speicher veerwendet)

Zeit jedoch ist schwieriger zu verstehen

Es folgt hier dann ein wichtiges Korollar!

[!Korollar]

unter Verwendung des Satz von Savitch gilt folgendes für das Verhältnis von PSPACE und NPSPACe

welches? #card

Da wir jetzt wissen, dass $NPSPACE(s(n))\subseteq SPACE(s(n{)}^2)$ eine Teilmenge sein kann, werden wir jetzt ferner sagen können, dass die Speicherkomplexität von NP und P gleich ist!

WAHNSINN, denn somit $$PSPACE=NPSPACE$$

–> Also wir verstehen Speicherplatz und wie dieser bei Nichtdeterministischen / deterministischen TMs aufgewandt wird, ganz gut!

Bezug zu P und NP ?

[!Feedback] Betrachtung der Komplexitätsklassenhierarchie

Unter allen vorherigen Definitionen und Lemmata können wir jetzt eine vollständige Kategorisierung der NP / P Komplexität beschreiben oder zumindest eine Annahme dieser

(Denn es ist ja weiterhin nicht gelöst!)

Wie ordnen wir jetzt DLOGSPACE, NP,P,PSPACE,NLOGSPACE,NPSPACE,DEXPTIME entsprechend? Was folgt hierbei bzgl ihrer Verhältnisse? #card

Wir beschreiben jetzt die fundamentale Komplexitätsklassenhierarchie der sequentiellen Berechnungen folgend: $$DLOGSPACE\subseteq NLOGSPACE\subseteq P\subseteq NP\subseteq PSPACE=NPSPACE\subseteq DEXPTIME$$

–> Wichtig: für keine einzige der Inklusionen $\subseteq$ weiß man, ob es eine echte Inklusion ist (also obs eine echte Teilmenge oder $=$ ist).

Über zwei echte Inklusionen weiß man bescheid: $DLOGSPACE\ne PSPACE$ und auch $P\ne DEXPTIME$

(Wo genau diese Ungleichheit in der Verkettung auftritt, weiß man aber nicht genau!)

NP ist nicht offensichtlich gleich EXP!

Was als weitere Folgerung gilt und ferner durch bestimmte Konstruktion bewiesen werden kann. Wir wollen dafür ein Theorem betrachten, was auf das Problem aufmerksam macht.

Zeithierarchietheorem

[!Satz] Zeithierarchietheorem

Es gilt: Für zeitkonstruierbare Funktionen $f,g$ mit $f(n)\log f(n)=o(g(n))$ gilt jetzt: $$DTIME(f(n))⫋DTIME(g(n))$$

Wie würden wir das beweisen können?Warum hilft ein Spezialfall dafür? #card

Wir betrachten dafür einen Spezialfall: $DTIME(n)⊊DTIME(n^{1.5})$ .

Dafür betrachten wir jetzt die DTM $D$, welche wir folgend konstruieren:

[!Lemma] Konstruktion

Auf Eingabe $x$

• Simuliere die universelle TM 112.14_universal_turing_machine $U$ auf $⟨M⟩=x$ für $\mid x{\mid }^{1.4}$ Schritte! (es müssen weniger sein, damit wir zeigen können, dass es dann nicht funktioniert!)
• Falls $U$ in der Zeit dann ein bit $b\in \{0,1\}$ schreibt, schreiben wir genau $1-b$ (Komplement) auf das Ausgabeband –> Falls nichts ausgegeben wird, schreiben wir einfach 0!

Wenden wir jetzt die DTM $D$ an, folgt:

• D hält in höchstens $n^1.4$ Schritten, also $L(D)\in DTIME(n^{1.5})$
• Wir zeigen aber noch $L(D)\notin DTIME(n)$, durch eine Diagonalisierung: Angenommen es gäbe eine DTM $D^{\prime }$, die $D(x)$ in der Zeit von $c\cdot n$ (c ist Konstante) berechnet.
  • (Wir wissen, dass die Simulation einer DTM auf $U$ die Zeitkomplexitäts von höchstens $c^{\prime }\cdot cn\log n$ aufweist. Hierbei ist $c^{\prime }$ unabhängig $n$!, sondern nur von der Bandzahl von Gamma und Sigma
  • Es gibt ferner abzählbar unendlich viele Realisiserungen von $D^{\prime }$ –> man kann also beliebig viele Gödelnummern für die TM generieren. Etwa durch das Hinzufügen von nutzlosen Zuständen, die nichts machen, aber die Implementierung verändern!
  • Es gibt dann ein $n_0$, sodass $n^{1.4}>c^{\prime }\cdot cn\log n\forall n\ge n_0$ .
  • Sei dann jetzt $x=⟨D^{\prime }⟩$ eine Gödelnummer von $D^{\prime }$ mit $\mid x|\ge n_0$
• Dann ist jetzt einerseits $D^{\prime }(x)=b=D(x)$ und weiterhin auch: $D(x)=1-b$ Was im Widerspruch steht!

Das volle Theorem nutzt, dass die Simulation auf $U$ höchstens logarithmischen Overhead hat.

(Und somit haben wir strikt mehr Möglichkeiten bzw mehr “Platz” bei der exponentiellen, also bei $DTIME(n)$)

Also in etwa: “Es gibt strikt mehr DTMS”, in $DTIME(n^{1.5})$ als in $DTIME(n)$

Folgerung | NP ist nicht einfach exponentiell schwer!

[!Important]

Aus dem Zeithierarchietheorem folgern wir jetzt, dass Probleme die eine komplette kombinatorische Enumeration erfordern - also ein exponentieller Vorgang! - nicht in polynomieller Zeit lösbar sind, also $P\ne EXP$.

Das sagt uns aber nicht wirklich viel aus! Es gibt Probleme, wo man nicht abkürzen kann und so etwa für eine deterministische TM das Problem exponentiell lösen kann.

Was wir somit weiterhin nicht beantworten können

Es gilt noch nicht, ob $P\ne NP$, denn dazu müsste man erst zeigen, dass $NP=EXP$ ( was aber nicht gesetzt ist)

Welche Folgerungen (4 haben wir beschrieben) kann man dann hieraus ziehen? Was beschreibt P, was NP was können wir über die Verifikation aussagen. was stimmt über den Speicheroverhead? #card

Wir erhalten jetzt 4 Folgerungen:

• $P$ ist die Klasse der Probleme, die von deterministischen TMS in polynomieller Zeit lösbar sind!
• $NP$ enthält alle Probleme, die von nicht-deterministischen TMs in polynomieller Zeit lösbar sind!
• Lösungen von Problemen in $NP$ sind von DTMs in polynomieller Zeit verifizierbar!
• Alle Probleme in $NP$ sind auch von DTMs in exponentieller Zeit lösbar - indem wir die Pfade, die auftreten können, einfach aneinanderhängen!
  • Dabei sind sie mit polynomiellen - quadratischen - Speicheroverhead lösbar, wie wir gezeigt haben!

Was, wenn $P=NP$ wäre?

Die Utopie, oder auch nicht?!

Angenommen wir wüssten, dass $P=NP$ ist, dann würde das bestimmte Folgerungen haben:

• die Kryptographie würder zerfallen, weil sie auf solchen schweren Problemen netsec_ElGamal und netSec_RSA aufbaut!
• Quantencomputing wäre egal, denn man wüsste dann $P=DEXPTIME$
• Beweise zu finden, wäre damit genauso schwer, wie sie zu verifizieren –> Mathematik von Menschen wäre damit egal, weil man alles maschinell finden lassen könnte!
• Alltagsprozesse könnten optimal laufen - 111.18_Graphen_Traversieren TSP etc. wären einfach zu lösen!
• Alle sechs Millennium-Probleme würden gelöst werden!

Und somit würden wir die Welt schon stark beeinflussen!

Aber was man schon sagen kann:

Forderung einer niedrigeren Ordnung

Wenn wir uns aktive Algorithmen anschauen - etwa auch wie sie funktionieren etc- dann können wir schon einsehen, dass es in den Laufzeiten verschiedene Verläufe gibt (logisch)

Betrachten wir etwa aktuelle Leistungsfähigkeiten von Supercomputern (Stand 2024).

Ideen:

• Eigentlich sind Lösungen nur spannend, wenn die gefundenen Algorithmen von niedrigem Polynomiellen Grad sind –> etwa $\mathcal{O}(n^6)$ (auch wenn das noch nicht soo gut ist, weils schnell wächst)

• Das heißt insbesondere die Algorithmen dürfen keine Vergleiche von Tupeln aus ihren $n$ Inputs machen –> wenn die Tupel von einer höheren Ordnung sind!

• Typischerweise ist es aber oft so, dass für ein Problem zunächst ein langsamer Algorithmus gefunden wird, etwa $\mathcal{O}(n^{20})$, welcher anschließend durch gute Umformung / Tricks etc reduziert werden kann auf $\mathcal{O}(n^3)$

[!Attention] Juris Hartmanis - Turing Award 1993

We know that P is different from NP.

We just don’t know how to prove it.

Es ist also bekannt, dass $P\ne NP$, nur halt noch nicht bewiesen!

Ansätze für $P\ne NP$

Versuch 1 | Diagonalisierung

Wir wollen damit argumentieren, warum $P\ne NP$ eventuell eintritt, indem wir etwa Mit Mengen argumentieren!

Um die Mächtigkeit einer Menge zu vergleichen, oder bestimmte Probleme bei der Konstruktion aufzuweisen, haben wir etwa schon die Diagonalisierung angeschaut, die meist mit einem Widerspruch zeigt, dass die Sprache eventuell überabzählbar ist.

Das Konzept wollen wir jetzt auch anwenden.

[!Beweis] Versuch 1 | Diagonalisierung

Wir könnten jetzt also versuchen zu zeigen, dass $NP$ mächtiger ist als $P$ –> etwa durch Diagonalisierung.

Was wäre hierbei unser Ansatz? Worin könnten wir ein Problem erhalten? #card

Die Diagonalisierung könnten wir etwa folgend umsetzen:

• Enumeriere alle DTMs $M_i$ in einer polynomiellen Laufzeti auf allen Eingaben $x$
• konstruiere jetzt eine NTM $N$ die auf der Eingabe $x$ die Diagonale $M_i(x)$ berechnet und ferner invertiert ( Also die vorhandenen Ausgaben an $ij$-ter Stelle)

Unter dieser Diagonalisierung verstehen wir dann eine Beweistechnik, bei welcher wir zwei Annahme verwenden:

1. Jede TM kann durch eine $⟨M⟩$ Gödelnummer kodiert werden
2. Jede TM kann auf der universellen TM $U$ - mit logarithmischen Overhead simuliert werden! (wie wir zuvor schon beschrieben haben.)

Problem was wir hierbei erhalten:

• Diese Definition ist nicht wirklich klar –> Denn sie betrachtet die internen Mechanismen der Berechnung nicht bzw. beschreibt sie nicht!

Versuch 2 | Orakelmaschine

[!Definition]

Wir wollen eine neue Maschine einführen, die eine normale TM $M$ “erweitert” indem sie noch ein weiteres Band, das Orakel-Band aufweist.

Wir sprechen hierbei von der Orakelmaschine.

Wie funktioniert sie, was für Zustände weist sie auf? Wie können wir eine neue Menge von Srachen beschreiben? #card

Die Orakelmaschine ist also eine erweiterte TM $M$, die einen Zugriff auf ein Orakel-Band hat, auf welchem einfach bestimmte Wörter der Sprache $O\in \{0,1{\}}^{\ast }$ stehen ( also einfach eine Auswahl von Wörtern aus einem gegebenen Alphabet)

Sie führt einen neuen Zustand $q_{orakel}$ ein:

• Wenn $M$ in den Zustand $q_{orakel}$ übergeht, dann springt sie in $q_{accept}$, wenn die Eingabe auf dem Band gerade $\in O$ - dem Orakelband - ist oder $q_{nein}$, falls $q\notin O$. $q$ ist hierbei der aktuelle Inhalt des Orakelbandes
• Wir beschreiben jetzt mit $M^0(x)$ die Ausgabe von $M$ auf $x$ mit einem Orakel $0$
• –> eine nicht-deterministische Orakel-maschine ist analog definiert!

Ferner gilt jetzt: Für jedes $0\subseteq \{0,1{\}}^{\ast }$ ist $P^0$ die Menge der Sprachen, die in polynomialer Zeit von einer deterministischen Orakelmaschine mit Orakel $0$ entschieden werden.

Ferner ist auch $N{P}^0$ analog definiert!

Wichtig: Durch diese Struktur lässt sich jetzt ein Teil von $P/NP$ aufteilen bzw charakterisieren!

Satz Baker | Gill | Solovay

[!Satz]

Betrachten wir ein Orakel $A,B\in \{0,1{\}}^{\ast }$

Was könnten wir dann über mögliche Problem in P,NP sagen? #card

Es gibt spezifische Orakel $A,B$, sodass dann: $$P^{A=}N{P}^{A\wedge }{P}^B\ne N{P}^B$$

Wir haben also die Möglichkeit bestimmte Subbereiche zu betrachten und darüber aussagen zu treffen.

Ferner sehen wir hier aber auch, dass es widersprüchliche Aussagen gibt - sowohl $=$ als auch $\ne$ treten auf - und somit haben wir weiterhin keine volle Aussage getroffen!

Relativierung

Mit Dem Satz Baker | Gill | Solovay wurde jetzt gezeigt, dass die beiden Annahmen der Diagonalisierung von TMs nicht ausreichen um $P\ne NP$ zu zeigen.

Damit ist diese Betrachtung relativ.

[!Example] Relativierung | Definition

Die Eigenschaft der Relativierung scheint hier also ähnlich / analog zur Beschreibung der Unabhängigkeit in der Mengenlehre zu sein –> $CH$ ist unabhängig von $ZFC$ (Die verschiedenen Axiom-Strukturen für die Mengenlehre)

Was können wir ferner über die Relativierung aussagen? Gibt es ein nicht-relativierendes Axiom, dass man zu 1 und 2 hinzufügen kann, um alle bekannten nicht relativierenden Ergebnisse zu beweisen? #card

Die Relativierung ist komplizierter, als die Unabhängigkeit der Mengenlehre, denn es gibt überabzählbar viele Orakel –> Genau wie es überazbählbar viele Sprachen über einem Alphabet gibt!

Damit wissen wir nicht, welche Orakel natürlich sind und welche nicht!

Es gibt ein nicht-relativierendes Axiom: Local Checkability

• in etwa, dass jeder Schritt einer TM nur eine konstante Menge an Bandzellen lesen oder ändern kann!

(Diese Idee ist ein Kandidat, und kann wohl bei der Anwtwort zur Frage $P=NP$ helfen. jedoch hilft uns das soweit nicht weiter!

Wenn $P=NP$ unbeweisbar ist?!

source

In this note we show that instances of problems which appear naturally in computer science cannot be answered in formalized set theory. We show, for example, that some relativized versions of the famous P = NP problem cannot be answered in formalized set theory, that explicit algorithms can be given whose running time is independent of the axioms of set theory, and that one can exhibit a specific context-free grammar G for which it cannot be proven in set theory that $L(G)={\Sigma }^{\ast }\vee L(G)\ne \Sigma \ast$.

Satz | Hartmnias & Hopcroft

[!Satz]

Es gilt: Ex existiert eine TM $M$, sodass die Wahrheit von $P^{L(M)}=N{P}^{L(M)}$ unabhängig von den ZFC Axiomen der Mengenlehre ist!

Dabei beschreibt $P^{L(M)}$ die Orakelklasse $P$ für das Orakel $L(M)$.

Was wäre ein Ansatz für den Beweis der Aussage? #card

Man könnte hierbei folgenden Beweis bzw. folgende Strategie anwenden:

Es gibt die Orakel $A,B$, sodass dan n$P^{A=}N{P}^A\wedge P^B\ne N{P}^B$ –> Man definiert dann $L(M)$ folgend:

• falls in ZFC ein Beweis für $P^{L(M)}=N{P}^{L(M)}$ existiert, dann wählen wir $L(M)=B^{\prime \prime }$ (mit technischen Details?)
• falls in ZFC ein Beweis für $P^{L(M)}\ne N{P}^{L(M)}$ existiert, dann wählen wir $L(M)=A^{\prime \prime }$

Damit würde sich ein Widerspruch ergeben und somit kann es einen solchen Beweis für ZFC nicht geben!

–> Damit ist die Mengentheorie dafür nicht anwendbar!

Ferner folgt:

Es könnte sein, dass $P=NP$ eine unentscheidbare Frage ist! Das wäre aber enttäuschender, als die unentscheidbaren Probleme der Berechenbarkeitstheorie denn PSO ist “greifbarer”.

Damit kommt philosophisch auf:

• Möchten wir in einer Welt leben, wo $P=NP$ ist
• oder wir leben in einer Welt $P\ne NP$

in beiden Fällen können wir es nicht beweisen!

Oder wie auch Lena-Schlipf 115.00_graphentheorie_anchor sagt:

[!Beweis] It seems a lot lot more difficult than expected!