3-p-und-np.tex

%!TEX root = 0-main.tex

% Author: Philipp Moers <soziflip@gmail.com> 




\chapter{NP und P} % (fold)
\label{cha:np_und_p}
        

\section{Padding}

\begin{definition}
    Sei $L \subseteq \Sigma^\ast$ eine Sprache.

    % (Blase: 2^?  ist die Paddingfunktion geht auch für andere P.fkt.)
    % TODO verstehen, anpassen, einkommentieren

    $$ padd(L) = \{1^l O x | x \in L, l = 2^{|x|} \} $$
\end{definition}


\begin{satz}
    
    Es gilt: 
    $ L \in DTIME(f(s^n)) $, dann ist
    $$ padd(L) \in DTIME(f(n)) $$
    Blase $f$ zeitkonstant und insbesondere $f(n) \geq n$

\end{satz}

\begin{beweis}
    
    Sei $T$ eine deterministische Turingmaschine für $L$ und
    % TODO \leq \in ?
    $DTIME_T(x) \leq \in x f(2^n)$

    Die folgende Maschine $T'$ entscheided $padd(L)$:

    Gegeben Eingabe $y$, schreibe $y + 1^l O x$ und prüfe ob $l = 2^{|x|}$
    geht in Zeit $\bigO(|y|)$

    Aufwand: 
    $c f(2^{|x|}) \leq c * f(|y|)$

    Gesamtaufwand:
    $\leq c * f(|y|) + |y|
    = \bigO(f(|y|))$

    falls $f(n) \geq n$ (zeitkonstruierbar)
\end{beweis}




\begin{satz}
    Umgekehrt gilt auch:

    Wenn $padd(L) \in DTIME(f(n))$
    dann $L \in DTIME(f(s^{n+1}))$
\end{satz}

\begin{beweis}
    Sei $T$ eine Turingmaschine für $padd(L)$
    mit $DTIME_T(y) \leq c f(|y|)$

    Wir bauen eine Maschine für $L$:
    Gegeben Eingabe $x$, bilde $y = 1^{2^{|x|}} O x $.

    Aufwand: $\bigO(2^{|x|})$
    Setze $T$ auf $y$ an.
    Aufwand: $c * f(|y|) = c * f(2^{|x|} + |x| + 1)$

    Gesamtaufwand:
    $\bigO(f(2^{|x|+1}))$
\end{beweis}




\section{Was wenn P = NP}

\begin{satz}
    Folgerung:
    $$\ComplexityClassP = \ComplexityClassNP \Rightarrow \ComplexityClassE = \ComplexityClassNE$$
\end{satz}
\begin{beweis}
    Sei $P = NP$
    und $L \in NE$ und $T$ eine Maschine mit Aufwand $n^{kk}$
    wobei $k$ fest, $n$ Länge der Eingabe.
    
    $L \in NTIME(n^{nk}) = NTIME((2^n)^k)$
    Also $padd(L) \in NTIME(2^k)$
    also $padd(L) \in  NP$ und nach Annahme $padd(L) \in P$

    Also $padd(L) \in DTIME(n^{k'})$
    also $L \in DTIME((2^{n+1})^{k'})
    = DTIME(2^{k'n + k'}) = DTIME(2^{k'n}) \subseteq E$
\end{beweis}



Slogan: Gleichheit von Komplexitätsklassen vererbt sich nach oben.

Mit anderen Paddingfunktion zeigt man ebenso:

$$ \ComplexityClassP = \ComplexityClassNP \Rightarrow \ComplexityClassEXP = \ComplexityClassNEXP $$
$$ \ComplexityClassE = \ComplexityClassNE \Rightarrow \ComplexityClassEXP = \ComplexityClassNEXP $$

Kontrapositiv ausgedrückt:

$$ \ComplexityClassE \neq \ComplexityClassNE \Rightarrow \ComplexityClassP \neq \ComplexityClassNP $$ etc.


Es koennte sein, dass $\ComplexityClassP \neq \ComplexityClassNP$ aber doch $\ComplexityClassE = \ComplexityClassNE$.

Slogan: Trennung von Komplexitätklassen vererbt sich (durch Padding) von oben nach unten.




\section{Sogenannte Effizienz}


$\ComplexityClassP$ wird gemeinhin gleichgesetzt mit effizienter Lösbarkeit.
    
Wachstumsverhalten:

  $p$ Polynom. $\Rightarrow$ 
  $$ \exists c > 0:   p(2n) \leq c * p(n) $$

  Bei Verdopplung des Inputs wird der Output also ver-$c$-facht.

  Häufig hat stures Durchprobieren, auch Bruteforcing genannt,
  exponentiellen und eine echte algorithmische Lösung hat polynomiellen Aufwand.











\datum{09.11.15}


\section{Polynomialzeitreduktionen}



\begin{definition}

    $f : \Sigma^\ast \rightarrow \Sigma^\ast $
    beziehungweise für Binärkodierung
    $f : \N \rightarrow \N $

    ist in \definiere{$\ComplexityClassFP$} (eine \definiere{in Polynomialzeit berechenbare Funktion}) genau dann, wenn eine polynomialzeitbeschränkte (deterministische) Transducer-Maschine existiert, die $f$ berechnet.

\end{definition}


Gegeben Input $x \in \Sigma^\ast$, dann hält die Maschine nach $\leq p(|x|)$ Schritten mit Ergebnis $f(x)$, wobei $p$ ein Polynom ist.

\begin{beispiel}
    
    \textbf{Musterbeispiele:}

    \begin{itemize}
        \item Alle Polynome sind in $\ComplexityClassFP$, zum Beispiel $f(x) = x^3 + 10x^2 + x$
        \item Charakteristische Funktionen aller Probleme in $\ComplexityClassP$ sind in $\ComplexityClassFP$.
        \item Matrixmultiplikation ist in $\ComplexityClassFP$.
    \end{itemize}

    \textbf{Gegenbeispiele:}

    \begin{itemize}
        \item $f(x) = 2^x$ ist nicht in $\ComplexityClassFP$, denn $|2^x| = x + 1 \geq 2^{|x| + 1} +  1 = \Omega(2^{|x|})$
        \item Charakteristische Funktionen von Problemen in $\ComplexityClassEXP \setminus \ComplexityClassP$  sind nicht in $\ComplexityClassFP$.
    \end{itemize}

    \textbf{Wahrscheinliches Gegenbeispiel:}

    $f(n) = \text{größter Teiler von } n \text{ außer } n \text{ selbst.}$
    Algorithmus: Alle Zahlen von 1 bis $n$ durchlaufen und testen, immer merken, wenn größerer Teiler gefunden.\\
    Laufzeit: $\Omega(n) = \Omega(2^{|n|})$ (Länge der Eingabe statt Zahl selbst)

\end{beispiel}




\begin{satz}
    $\ComplexityClassFP$ ist unter Komposition (Hintereinanderausführung) abgeschlossen.\\
\end{satz}
\begin{beweis}
    
    Seien $ f: \Sigma^\ast \rightarrow \Sigma^\ast, g : \Sigma^\ast \rightarrow \Sigma^\ast \in \ComplexityClassFP $

    Wir definieren $h(x) = g(f(x))$

    Programm für $h$: $y = f(x);\ z = g(y);\ return\ z;$\\
    Gesamtaufwand: $O(p_f(|x|) + p_g(p_f(|x|))$, wobei $p_f$ und $p_g$ Polynome sind, die die Laufzeit für Algorithmen für $f$ bzw. $g$ beschränken.
\end{beweis}




\begin{definition}

    \definiere{Polynomielle Reduzierbarkeit}

    Seien $L_1, L_2a \subseteq \Sigma^\ast$.

    Wir sagen $L_1$ ist polynomiell auf $L_2$ reduzierbar (\definiere{$\ComplexityClassFP$-reduzierbar}) genau dann, wenn $f \in \ComplexityClassFP$ existiert, sodass $x \in L_1 \Leftrightarrow f(x) \in L_2$.

    Aus Algorithmus für $L_2$ erhält man einen für $L_1$, indem man $f(x)$ berechnet und prüft, ob das Ergebnis in $L_2$ liegt.

    In Zeichen: $L_1 \leq_p L_2$ oder $L_1 \leq L_2$, auch $f: L_1 \leq L_2$

\end{definition}


\begin{beispiel}
    
    3COL = $\{ G = (V,E)\ |\ G \text{ kann mit 3 Farben gefärbt werden, d.\,h. } \exists c: V \rightarrow \{r,g,b\} \text{ sodass } \forall (u, u') \in E: c(v) \neq c(u') \}$

    SAT = $\{ \phi\ |\ \phi \text{ aussagenlogische Formel die erfüllbar ist} \}$


    Behauptung: 3COL $\leq$ SAT



    % $f((V,E)) = (\bigwedge \bigvee         x_{v,y}  )      \land      \bigwedge   \bigwedge    \bigwedge      x_{v,c} \rightarrow \neg x_{v,c'}$
    %             v \in V    y \in r,g,b                               v \in V      c \in r,g,b    c' \in r,g,b
    %                                                                                               c \neq c'

    %             $ \land    \bigwedge        \bigwedge         x_{v,y} \rightarrow \neg x_{v', y}$
    %                        (v,v') \in E     y \in {r,g,b}


    $$f((V,E)) = \left(     \bigwedge_{v \in V} \bigvee_{y \in \{r,g,b\}}    x_{v,y}    \right)         \land     $$ 

    $$ \left(     \bigwedge_{v \in V} \bigwedge_{c \in \{r,g,b\}} \bigwedge_{c' \in \{r,g,b\}}      x_{v,c} \rightarrow \neg x_{v,c'} \right)       \land     $$

    $$ \left(     \bigwedge_{(v,v') \in E} \bigwedge_{y \in \{r,g,b\}}    x_{v,y} \rightarrow \neg x_{v', y} \right) $$
                                


    Offensichtlich ist $f \in \ComplexityClassFP$ und $G \in \text{ 3COL } \Leftrightarrow f(G) \in \text{ SAT }$,\\ also 3COL $\leq$ SAT.

\end{beispiel}



\begin{beispiel}
    
    KNFSAT := wie SAT, aber auf konjunktive Normalform eingeschränkt.

    Es gilt trivialerweise KNFSAT $\leq$ SAT, aber auch SAT $\leq$ KNFSAT (Durch Einführung von Abkürzungen von Teilformeln).

\end{beispiel}

\begin{beispiel}
    
    3SAT := KNFSAT eingeschränkt auf Klauseln mit 3 Literalen.

    Es gilt KNFSAT $\leq$ 3SAT.

    Man kennt keine Reduktion von 3SAT auf 2SAT.

\end{beispiel}


\begin{beispiel}
    
    NODE-COVER := $\{ G = (V,E), n\ |\ \exists U \subseteq V: |U| \leq n \text{ und } \forall (v,v') \in E: v \in U \lor v' \in U \}$

    Es gilt NODE-COVER $\leq$ KNFSAT.

    und -- was schwieriger zu zeigen ist -- KNFSAT $\leq$ NODE-COVER:

    Gegeben: KNF $\phi$ mit $m$ Variablen $x_1 \dots x_m$ und $k$ Klauseln $C_1 \dots C_k$ wobei $C_j = l_{j,1} \lor \dots \lor l_{j,k}$\\
    Falls 3SAT, so sind alle $k_j = 3$.\\
    Die $l_{j,i}$ sind Literale, d.\,h. negierte oder nicht-negierte Variablen.

    Wir konstruieren Graphen $G = (V,E)$ wie folgt:
    \begin{itemize}
        \item Für jede Variable $x_t$ zwei Knoten $x_t, \neg x_t$
        \item Für jede Klausel $C_j$ $k_j$ Knoten $(l_{j,1}) \dots (l_{j,k})$,\\ Insgesamt $2m \Sigma_{j=1}^k k_j$ Knoten
        \item Kanten: 
        \begin{itemize}
            \item $(x_t, \neg x_t)$
            \item Vollständiger Graph für $l_{j,1} \text{ bis } l_{j,k}$
            \item $(x_t, l_{j,i})$ bzw. $(\neg x_t, l_{j,i})$, falls $l_{j,i} = x_t$ bzw. $l_{j,i} = \neg x_t$
        \end{itemize}
    \end{itemize}

\end{beispiel}





\section{NP-Härte und NP-Vollständigkeit}


\begin{definition}
    
    $L \subseteq \Sigma^\ast$ ist \definiere{$\ComplexityClassNP$-hart} ($\ComplexityClassNP$-schwer, $\ComplexityClassNP$-schwierig) genau dann, wenn 

    $$ \forall L' \in \ComplexityClassNP: L' \leq_p L $$

\end{definition}


\begin{satz}
    HALT (Halteproblem) ist NP-hart.
\end{satz}
\begin{beweis}
    Gegeben: $L' \in \ComplexityClassNP$. Baue deterministische Turingmaschine $M$, sodass $M(x)$ hält genau dann, wenn $x \in L'$ Brute-force Suche, Laufzeit exponentiell.\\
    $x \in L' \Leftrightarrow (M, x) \in \text{ HALT } $\\
    also ist $f(x) = (M,x)$ eine Reduktion von $L'$ auf HALT $f: L' \leq \text{ HALT }$.
\end{beweis}



\begin{definition}

    $L \subseteq \Sigma^\ast$ ist \definiere{NP-vollständig} genau dann, wenn $L$ NP-hart ist und $L \in \ComplexityClassNP$.

\end{definition}


\begin{satz}
    HALT $\notin \ComplexityClassNP$.
\end{satz}



\begin{satz}
    \definiere{Satz von Cook}

    SAT ist NP-vollständig.
\end{satz}

\begin{beweis}
    
    SAT $\in \ComplexityClassNP$: trivial.

    Sei $L \in \ComplexityClassNP$ gegeben und o.\,B.\,d.\,A. $M$ eine nichtdeterministische Turingmaschine für $L$ mit einem Band $M = (\Sigma, Q, q_0, F, I)$ und $p$ ein Polynom, das die Laufzeit von $M$ beschränkt.
    Gegeben weiterhin $x = x_1 \dots x_n$ Input.

    Gesucht: aussagenlogische Formel $\phi = f(x)$, sodass $\phi$ erfüllbar ist genau dann, wenn $M$ akzeptiert $x$. $q$ muss aus $x$ in polynomieller Zeit berechenbar sein, d.\,h. $f \in \ComplexityClassFP$.

    $M$ akzeptiert $x$ genau dann, wenn eine akzeptierende Berechnung von $M$ auf $x$ existiert. Solch eine Berechnung hat höchstens $p(n)$ Schritte und o.\,B.\,d.\,A. genau $p(n)$ Schritte. Die Bandbeschriftung zu jedem dieser $p(n)$ Schritte besteht aus höchstens $p(n)$ Symbolen und o.\,B.\,d.\,A. genau $p(n)$ Symbolen.

    Die Formel $\phi$ verwendet die Variablen 
    \begin{itemize}
        \item $Q_t^i$: Zur Zeit $t$ ist $M$ im Zustand $i$.
        \item $P_{s,t}^i$: Zur Zeit $t$ enthält Bandposition $s$ das $i$-te Symbol.
        \item $S_{s,t}$: Zur Zeit $t$ ist der Kopf in Position $s$.
    \end{itemize}

    $$ q = A \land B \land C \land D \land E \land F $$

    \textit{Details im Buch\dots}

\end{beweis}


3SAT, NODE-COVER sind auch NP-vollständig.

Allgemein gilt: $L$ NP-vollständig und $L' \in \ComplexityClassNP, L \leq L'$ 
so folgt $L'$ NP-vollständig.


\textbf{Anmerkung:}
$\leq$ ist transitiv, da $\ComplexityClassFP$ unter Komposition abgeschlossen ist.

\textbf{Anmerkung:}
3COL, TRAVELINGSALESMAN, SUBSETSUM etc. sind auch NP-vollständig.












\datum{12.11.15}


\section{Etwas zwischen P und NP}



\begin{satz}
    
    \definiere{Satz von Ladner}

    Falls $\ComplexityClassP \neq \ComplexityClassNP$, dann

    $$ \exists A \in \ComplexityClassNP \setminus \ComplexityClassP: A \text{ nicht NP-vollständig.} $$

    $A$ liegt also echt zwischen $\ComplexityClassP$ und NP-vollständig.

    
\end{satz}



\begin{definition}

    \definiere{Diagonalisierung}
    
    Um zu zeigen, dass eine Sprache $A$ nicht in einer Klasse $\mathcal{C}$ ist, beziehungweise um solch ein $A$ zu konstruieren, kann man eine effektive (FP) Aufzählung von Turingmaschine $(M_i)_i$ verwenden, sodass $\mathcal{C} = \{ L(M_i)\ |\ i \geq 0 \}$  und dann dafür sorgen, beziehungweise zeigen, dass $\forall i: A \neq L(M_i)$ beziehungweise $\forall i: A \triangle L(M_i) \neq 0$.\\
    Das heißt $\forall i \exists x: \left(x \in A \land x \notin L(M_i) \right) \lor \left( x \notin A \land x \in L(M_i) \right)$

\end{definition}


\begin{lemma}
    
    Es existiert eine FP-Funktion $i \mapsto M_i$, sodass $DTIME_{M_i}(x) \leq (|x| + 2)^2$ und $P = \{ L(M_i)\ |\ i \geq 0 \}$.

\end{lemma}

\begin{lemma}
    
    Es existiert eine FP-Funktion $i \mapsto f_i$ wobei $f_i$ eine Übersetzermaschine ist und $FP = \{ f_i\ |\ i \geq 0 \}$ und $DTIME_{f_i}(x) \leq (|x| + 2)^i$. Insbesondere $|f_i(x)| \leq (|x| + 2)^i$.

\end{lemma}

Es ist klar, dass $A \in \ComplexityClassNP$ aber $A \notin \ComplexityClassP$ und $A$ nicht NP-vollständig, wenn
\begin{itemize}
    \item $A \in NP$
    \item $\forall i \exists x: x \in A \triangle L(M_i)$
    \item $\forall i \exists x: x \in SAT \land f_i(x) \notin A \text{ oder } x \notin SAT \land f_i(x) \in A$
\end{itemize}

Das heißt $f_i$ ist keine Reduktion von $SAT$ auf $A$.





Wir konstruieren $A$ in der folgenden Form:

$$ A = \{  x \ |\   x \in SAT  \land   f(|x|) \text{ gerade.}  \} $$

$f$ wird sogleich rekursiv definiert derart, dass dieses $A$ die Bedingungen 1, 2 und 3 erfüllt.

Man sollte also versuchen sicherzustellen, dass 

\begin{itemize}
    \item 
    $f(n) in ZEit p(n)$ berechenbar für Polynom $p$ (Bedingung 1).

    \item 
    Für alle $i$ existiert $x$ mit \\
    $x \in SAT$ und $f(|x|)$ gerade und $x \notin L(M_i)$\\
    oder\\
    ($ x \notin SAT$ oder $f(|x|)$ ungerade ) und $x \in L(M_i)$\\

    \item 
    Für alle $i$ existiert $x$, sodass
    $x \in SAT$ und ($f(|f_i(x)|)$ ungerade oder $f_i(x) \notin SAT$\\
    oder\\
    $x \notin SAT$ und $f(|f_i(x)|)$ gerade und $f_i(x) \in SAT$\\

\end{itemize}


$f$ wird jetzt rekursiv definiert.\\
Wir schreiben $A_f = \{ x \ |\   x \in SAT  \land  f_(|x| \text{ gerade.}  \}$

\begin{equation*}
\begin{split}
f(n+1) = 
    IF    &\ \ (2 + \log \log n)^{f(n)} \geq \log n \\
    THEN  &\ \ f(n) \\
    ELIF  &\ \ \exists x: |x| \leq \log \log n \text{ und } x \in L(M_i) \land x \notin A_f \text{ oder } x \notin L(M_i) \land x \in A_f \\
    THEN  &\ \ f(n) + 1 \text{ ebe } f(n) \\
    ELIF  &\ \ \exists x: |x| \leq \log \log n \\
    THEN  &\ \ f(n) + 1
\end{split}
\end{equation*}

Um $f(n+1)$ zu berechnen wird rekursiv nur auf Werte $f(m)$ mit $m \leq n$ zugegriffen, also ist $f$ eine totale Funktion.

Es genügt, ein Polynom $p(n)$ zu finden, sodass in Zeit $p(n)$ der Wert $f(n+1)$ aus $f(0), f(1), \dots f(n)$ bestimmt werden kann.\\
Die Laufzeit für $f(n)$ ist nämlich dann $\bigO(\Sigma_{m < n} p(m)) = poly(n)$.


Offensichtlich ist $A = A_f \neq L(M_i)$, falls $f(n) = 2i+1$ für ein $n$, denn dann war $f(n') = 2i$ für ein $n' < n$ und $f(n'+1) = 2i+1$ also die Suche in Fall 2 erfolgreich.

Ebenso ist $f_i$ keine Reduktion: $SAT \leq A_f$, falls $f(n) = (2i+1)+1$ für ein $n$.

Das heißt wir müssen zeigen, dass $f$ surjektiv ist, d.\,h. dass jeder Fall irgendwann erfolgreich abgeschlossen wird.

% Für festes $d$ wächst $(2 + \log n)^d$ langsamer als $n$, also wächst auch $ $ blabla

\textit{Details dazu auf der Website.}










\datum{16.11.15}


\section{Orakel-Turingmaschinen}


Orakel-Turingmaschinen als Mittel zu zeigen, dass die Beweismethoden Diagonalisierung\footnote{zum Beispiel benutzt für $\ComplexityClassNP \subseteq \ComplexityClassEXP$} und Simulation\footnote{zum Beispiel benutzt für $\ComplexityClassP \subset \ComplexityClassEXP$ (Ladner)} nicht helfen, um $\ComplexityClassP = \ComplexityClassNP$ zu entscheiden.



\begin{definition}
    
    Eine \definiere{Orakel-Turingmaschine} $T$ hat ein zusätzliches Band (Orakelband) und drei zusätzliche Zustände $q_Q$ (Frage), $q_{yes}$, $q_{no}$ (Antwort).

    Ist $A \subseteq \Sigma^\ast$, dann definiert man Berechnungen $T^A(x)$ von $T$ auf $x$ mit Orakel $A$ wie folgt:
    \begin{itemize}
        \item Wie üblich mit der zusätzlichen Regel:\\
            Falls $T$ in $q_Q$ so wird $T$ in Zustand $q_{yes}$, $q_{no}$ versetzt und zwar in einem Schritt, je nach dem, ob die aktuelle Beschriftung $z \in \Sigma^\ast$ des Orakelbands (Anfrage/Query) in $A$ ist ($q_{yes}$) oder nicht ($q_{no}$).
    \end{itemize}
    Man schreibt $L^A(T)$ oder $L(T^A)$ für die von $T$ akzeptierte Sprache, falls Anfragen gemäß $A$ beantwortet werden.

\end{definition}




\begin{beispiel}
    
    Sei $STCONN = \{ (G, s, t) \ |\  \exists \text{ Pfad von } s \text{ nach } t \ \ \in G \} $

    Feststellen, ob ein Graph $G$ einen nichttrivialen Zyklus enthält. Zähle alle Paare $(u,v)$ auf und frage jeweils $(G, u, v)$ und $(G, v, u)$ ab.

    Damit ist eine Maschine $T$ beschrieben, sodass $CYCLE = L^{STCONN}(T)$.\\
    Die Laufzeit von $T$ ist $|G|^2$ (insbesondere polynomiell). Es ist also $CYCLE \in P^{STCONN}$. (Definition unten)\\
    Nachdem nun $STCONN \in \ComplexityClassP$ folgt $CYCLE \in \ComplexityClassP$.

\end{beispiel}


\begin{definition}

    Sei $A \subseteq \Sigma^\ast$.

    Man definiert $\ComplexityClassP^A$ als die Menge aller Sprachen $L$ sodass eine deterministische Turingmaschine $T$ existiert mit $L = L^A(T)$ und $DTIME(T^A(x)) \leq p(|x|)$ für ein Polynom $p$.

    Analog $\ComplexityClassNP^A$.
    
\end{definition}

\textbf{Beobachtung:}
$A \in \ComplexityClassP \Rightarrow \ComplexityClassP^A = \ComplexityClassP \land \ComplexityClassNP^A = \ComplexityClassNP$.

    
\begin{beispiel}
    
    $SAT \in \ComplexityClassP^{SAT}$

    $NODE-COVER \in \ComplexityClassP^{SAT}$

    $\ComplexityClassNP \in \ComplexityClassP^{SAT}$


    $ TAUT = \{ \phi \ |\  \phi \text{ allgemeingültig} \} \in \ComplexityClassP^{\ComplexityClassNP}$


    $ IMPL = \{ (\phi, \psi) \ |\  \phi \text{ allgemeingültig} \Rightarrow \psi \text{ allgemeingültig} \} \in \ComplexityClassP^{\ComplexityClassNP} $


    $ CIRCUIT-MIN = \{  (\text{Schaltkreis } C,  A) \ | \ 
            \text{Schaltkreis } C' \text{ der Größe } \leq k \text{ und } C \equiv C' \}  \in \ComplexityClassNP^{SAT}$

\end{beispiel}



Wr zeigen jetzt die folgenden zwei Sätze, aufgrund derer kein Beweis für $\ComplexityClassP = \ComplexityClassNP$ oder $\ComplexityClassP \neq \ComplexityClassNP$ existieren kann, welcher in Gegenwart von Orakeln auch funktioniert:

\begin{satz}
    
    $$ \exists A \in \Sigma^\ast: \ComplexityClassP^A = \ComplexityClassNP^A $$

\end{satz}

\begin{beweis}
    
    $A = \{ ( T, x, 0^k )  \ |\  
        \text{ deterministische Turingmaschine } T \text{ akzeptiert } x \text{ und benutt dabei } \leq k \text{ Bandzellen}  \}
    $

    $A$ ist offensichtlich entscheidbar.

    Sei $T$ eine nichtdeterministische Orakel-Turingmaschine und $p(n)$ ein Polynom, das die Laufzeit von $T$ beschränkt und somit auch die Größe aller Orakelanfragen.\\
    Wir müssen eine deterministische polynomiell zeitbeschränkte Turingmaschine $T'$ mit Orakel $A$ bauen, sodass $L^A(T') = L^A(T)$.

    Zunächst konstruieren wir eine deterministische Turingmaschine $T_{HILF}$, die ohne Orakelbenutzung die Sprache $L^A(T)$ entscheidet, indem alle Orakelanfragen ``mit Bordmitteln'' (also selbst) beantwortet werden unter Verwendung der Entscheidbarkeit von $A$.

    Vollständige Berechnungssequenzen einer Berechnung, deren Bandplatz $\leq k$ ist und $t$ Schritte lang ist, benötigen Platz $\bigO(k*t)$.\\
    Orakelanfragen einer Berechnung von $T$ auf $x$ (Eingabe) haben die Form $(S, y, 0^k)$ wobei $|S|, |y|, k \leq p(|x|)$.\\
    Wir verwenden also jetzt 3 Hilfsbänder, eines für die nichtdeterministische Berechnung von $T$ auf $x$, die wir der Reihe nach alle simulieren, eines für Orakelanfragen, eines für die Beantwortung der Orakelanfragen.\\
    Diese Maschine ist deterministisch und benötigt auf ihren Bändern höchstens $q(|x|)$ Platz, wobei $q$ ein von $p$ abgeleitetes Polynom ist (in etwa $q(n) = \bigO(p(n)^2$).\\

    Die eigentlichte Maschine $T'$ arbeitet jetzt wie folgt:\\
    Gegeben Eingabe $x$, schreibe $(T_{HILF}, x, O^{q(|x|)})$ auf das Orakelband. Falls $q_{yes}$, dann akzeptiere. Falls $q_{nein}$, dann verwerfe.

\end{beweis}


\begin{satz}
    
    $$ \exists B \in \Sigma^\ast: \ComplexityClassP^B \neq \ComplexityClassNP^B $$

\end{satz}

\begin{beweis}
    
    Falls $B \subseteq \Sigma^\ast$, 
    definiere $L_B = \{  0^k \ |\   \exists x \in \Sigma^\ast: |x| = k \land x \in B  \} $ \\
    Offensichtlich ist $L_B \in \ComplexityClassNP^B$, egal was $B$ ist.

    Es gilt jetzt, $B$ so zu wählen, dass für jede polynomiell zeitbeschränkte deterministische Orakel-Turingmaschine gitl: $L_B \neq L^B(T)$.

    Sei $i \mapsto T_i$ eine effektive Aufzählung von Orakel-Turingmaschinen, sodass $DTIME(T_i^x(x)) \leq |x|^i + i$ (alternativ $(|x| + 2)^i$ wie letztes Mal).\\
    Für alle deterministischen Orakel-Turingmaschinen $S$ und alle Orakel $x$ muss $i$ existieren, sodass $L(S^x) = L(T_i^x)$. $T_i$ ist die durch $i$ beschriebene Orakel-Turingmaschine künstlich auf Laufzeit $n^i + i$ beschränkt. Jetzt muss also für jedes $i$ ein $n_i$ existieren, sodass $T_i^B(0^{n_i})$ akzeptiert und $B$ enthält kein Wort der Länge $n_i$ (dann ist nämlich $0^{n_i} \notin L_B$), oder aber $T_i^B(0^{n_i})$ verwirft und $B$ enthält ein Wort $x_i$ mit $|x_i| = n_i$, denn dann ist $0^{n_i} \in L_B$.\\
    Dann ist in der Tat $L_B \notin \ComplexityClassP^B$.

    \textbf{Beobachtung:}
    Wenn $T_i^X(x)$ nach $t$ Schritten hält und $U$ aus Wörtern $y$ mit $|y| > t$ besteht, dann gilt 
    $T_i^{X \cup U}(x) \text{ akzeptiert }  \Leftrightarrow  \ T_i^X(x) \text{ akzeptiert}$.


\datum{19.11.15}

    
    Wir definieren rekursiv $n_i \in \N, B(i) \subseteq \Sigma^\ast, \Sigma = \{0,1\}, n_0 = 0, B(0) = \emptyset$
    \\
    Falls $B(0), \dots, B(i-1)$ schon definiert, definiere $n_i, B(i)$ so, dass gilt $\exists x: |x| = n_i \in B(i) \Leftrightarrow T_i^{B(i)}(0^{n_i} \text{ akzeptiert nicht}$.
    \\
    Außerdem sollte $T_i(0^{n_i})$ keine Elemente von $B(j) j>i$ anfragen.
    \\
    $B = \bigcup_{i \geq 0} B(i)$

    Es gilt dann $T_i^B(0^{n_i}) \text{ akzeptiert nicht } \Leftrightarrow T_i^{B(i)}(0^{n_i}) \text{ akzeptiert nicht } \Leftrightarrow 0^{n_i} \in L_{B(i)} \Leftrightarrow 0^{n_i} \in L_b$ (Falls wir zusätzlich dafür sorgen, dass $B(j)$ mit $j \geq i$ keine Elemente der Länge $n_i$ enthält.)

    Allgemein:
    $ B(i) =
    \begin{cases}
        B(i-1)              & , falls \dots     \\
        B(i-1) \cup \{x\}   & , falls \dots     \\
    \end{cases}
    $

    $n_i B(i) \in n_{i-1}(i-1)$
    $n_i$ sodass
    \begin{itemize}
        \item $n_i > n_{i-1}^{i-1} + i-1$ (Größer als die Laufzeit von $T_{i-1}(0^{n_{i-1}})$ und $T_j(0^{n_j})$ für $j < i$.)
        \item $2^{n_i} > n_i^i + i$ (da $2^x$ schneller wächst als $x^i+i$.)
    \end{itemize}
    Es gibt also mehr Wörter $x$ mit $|x| = n_i$ als die Laufzeit von $T_{i}(0^{n_i})$.

    Halbkonkrete Ausführung dieser Aufzählung für die ersten drei Schritte:
    \\
    $n_0 = 0, B(0) = \emptyset, n_1 > 0^0 + 0, 2^{n_1} > n_1 + 1$
    \\
    Rechne $T_1^{B(0)}(000)$. Wir nehmen an, dass nicht akzeptiert wird. Also $B(1) = B(0) = \emptyset$
    \\
    $n_2 > n_1^1 = 4, 2^{n_2} > n_2^2 + 2, \leadsto n_2 = 5$
    Rechne $T_2^{B(1)}(00000)$. Wir nehmen an, dass akzeptiert wird. Diese Rechnung dauerte $\leq 5^2 + 2 = 27$ Schritte. Es gibt 32 Wörter der Länge 5. Sei $x$ eines, das nicht abgefragt wurde. $x = 10110$. $B(2) = B(1) \cup \{10110\} = \{10110\}$
    \\
    $n_3 > 27, 2^{n_3} > n_3^3 + 3, \leadsto n_3 = 28$
    Rechne $T_3^{B(2)}(0^{28})$. Wir nehmen an, dass nicht akzeptiert wird. Also $B(1) = B(0) = \emptyset$
    \\
    \dots

    Invariante $B \cap \{ x \ |\  |x| \leq n_i \}  = B(i)$
    \\
    Rechenzeit von $T_i(0^{n_i}) < n_{i+1}$ ($> n_i^i + i$)

    $B$ unterscheidet sich von $B(i-1)$ nur durch Wörter die von $T_i^{B(i-1)}(0^{n_i})$ nicht angefragt werden. Entweder, da sie länger sind als die Rechenzeit oder von der Länge $n_i$ sind, aber so gewählt wurden, dass sie nicht gefragt werden.

    $T_i^B(0^{n_i}) \text{ akzeptiert } \\\Leftrightarrow 
    T_i^{B(i-1)}(0^{n_i}) \text{ akzeptiert } \\\Leftrightarrow 
    \neg \exists x \in B(i): |x| = n_i \\\Leftrightarrow 
    0^{n_i} \notin L_B
    $

    Das heißt $L(T_i^B) \neq L_B$

    $L_B \notin \ComplexityClassP^B$

\end{beweis}





\section{Polynomielle Hierarchie}

\begin{definition}
    
    $co\text{--}\phi = \{ L \subseteq \Sigma^\ast \ |\ \Sigma^\ast \setminus L \in \phi  \}$

\end{definition}

$co\text{--}\ComplexityClassP = \ComplexityClassP$

$co\text{--}\ComplexityClassNP$ ist nicht offensichtlich gleich $\ComplexityClassNP$ wegen der asymmetrischen Akzeptanzbedingungen bei Nichtdeterminismus.


\begin{definition}
    
    Die \definiere{polynielle Hierarchie} (PH):

    $\Delta_0^\ComplexityClassP = \ComplexityClassP$

    $\Sigma_0^\ComplexityClassP = \Pi_0^\ComplexityClassP = \ComplexityClassP$


    
    $\Sigma_1^\ComplexityClassP = \ComplexityClassNP$

    $\Pi^\ComplexityClassP = co\text{--}\ComplexityClassNP$

    Das soll andeuten, dass von der PH die Rede ist. Es hat nicht mit einem Exponenten oder Orakel zu tun.

\end{definition}


    

% \begin{beispiel}

%     $TAUT = \{ \psi \ |\  \psi \text{ allgemeingültig} \} \in co\text{--}\ComplexityClassNP$

%     $\Sigma^\ast \setminus TAUT = \{ \psi \ |\  \psi \text{ keine syntaktisch richtige Formel } \lor \} \in co\text{--}\ComplexityClassNP$

%     da war die tafel schon gewischt. naja.

% \end{beispiel}


\begin{definition}
    
    \definiere{relativierte Quantoren}


    Notation: $\exists_n x . A(x) \equiv \exists x \in \Sigma^\ast . |x| \leq n \land A(x)$

    Ebenso: $\forall_n x . A(x) \equiv \forall x \in \Sigma^\ast . |x| \leq n \Rightarrow A(x)$

    Außerdem: $\neg \exists_n x . A(x) \Leftrightarrow \forall_n x . \neg A(x)$

    und: $\neg \forall_n x . A(x) \Leftrightarrow \exists_n x . \neg A(x)$

\end{definition}

% Aus der Definition von $\ComplexityClassNP$ folgt

% man ich bin zu langsam und checken tu ichs auch nicht


\begin{definition}
    
    Die weitere \definiere{polynielle Hierarchie} (PH):

    $\Sigma_2^\ComplexityClassP = \ComplexityClassNP^{SAT} = \ComplexityClassNP^{\ComplexityClassNP}$

    $\Pi_2^\ComplexityClassP = co\text{--}\ComplexityClassNP^{SAT} = co\text{--}\ComplexityClassNP^{\ComplexityClassNP}$

    $\Delta_2^\ComplexityClassP = \ComplexityClassP^{SAT} = \ComplexityClassP^{\ComplexityClassNP}$

    $\Sigma_{n+1}^\ComplexityClassP = \ComplexityClassNP^{\Sigma_n^\ComplexityClassP}$

    $\Pi_{n+1}^\ComplexityClassP = co\text{--}\ComplexityClassNP^{\Sigma_n^\ComplexityClassP}$

    $\Delta_{n+1}^\ComplexityClassP = \ComplexityClassP^{\Sigma_n^\ComplexityClassP}$

    \textit{Anmerkung:}\\
    $\ComplexityClassNP^\phi = \bigcup_{X \in \phi} \ComplexityClassNP^X$


\end{definition}





\section{Kollabieren der polynomiellen Hierarchie}



Falls $\ComplexityClassP = \ComplexityClassNP$, so folgt $\Sigma_n^\ComplexityClassP = \ComplexityClassP$.

Im allgemeinen gilt: Falls $\Sigma_{n+1}^\ComplexityClassP = \Sigma_n^\ComplexityClassP$ für ein bestimmtes $n$, dann auch $\Sigma_{n'}^\ComplexityClassP = \Sigma_n^\ComplexityClassP$ für alle $n' \geq n$. Man sagt dann PH kollabiere auf der $n$. Stufe.





\datum{23.11.15}


\begin{satz}
    
    $L \in \Sigma_2^\ComplexityClassP \Leftrightarrow \\
    \exists L' \in \ComplexityClassP, \text{ Polynom } p:
    x \in L \Leftrightarrow \exists_{p(|x|)} y . \forall_{p(|x|)} z . (x,y,z) \in L'$

\end{satz}

\begin{beweis}
    
    \begin{itemize}

        % wie
        %       \item ``$\subseteq$'':
        % mit quotes finde ich schöner
        
        \item ``$\Leftarrow$'':

            Seien $L' \in \ComplexityClassP$, $p$ Polynom vorgegeben.\\

            Gesucht: nichtdeterministische Polynomialzeit-Orakel-Turingmaschine $M$ sodass $M$ mit geeignetem $\ComplexityClassNP$-Orakel die Sprache $L$ entscheide.

            $L'' = \{ (x,y) \ |\  \exists_{p(|x|)} z . (x,y,z) \notin L' \} $

            $L'' \in \ComplexityClassNP$ (Rate $z$ und prüfe $(x,y,z) \notin L'$)

            $x \in L \Leftrightarrow \exists_{p(|x|)} y . (x,y) \notin L'' $

            Die Maschine $M$ rät also $y$ und prüft $(x,y) \notin L''$ mit Orakel für $L''$.

        \item ``$\Rightarrow$'':

            Sei $M$ eine nichtdeterministische durch $p(n)$ laufzeitbeschränkte Turingmaschine mit Orakel $X \in \ComplexityClassNP$, z.B. $X = SAT$, $L = L(M)$

            Es ist $x \in L = L(M)$ genau dann, wenn \\
            $\exists \text{ Lauf } y \text{ von } M \text{ auf }: 
            M \text{ akzeptiert } x \land |y| \leq q(|x|)$ \\
            wobei $q$ ein Polynom ist mit $q(n) = \bigO(p(n)^2)$

            Um zu prüfen, ob $y$ tatsächlich ein LAuf ist und noch dazu akzeptierend, muss neben allem möglichen, was in polynomieller Zeit geht, z.B. 
            \begin{itemize}
                \item Folgefkonfigurationen jeweils gemäß der Maschinentafel ($\delta_M$) aus Vorgängerkonfigurationen enthalten,
                \item Am Anfang Startzustand, am Ende akzeptierender Zustand,
                \item Input okay in Startkonfiguration kopiert,
            \end{itemize}
            auch geprüft werden, dass alle Orakelanfragen richtig beantwortet wurden.

            \dots 

            und

            $\exists \eta . \eta_i$ erfüllt die $i.$ \underline{positiv} beantwortete Orakelanfrage $q_i \in SAT$.

            und

            $\forall \rho . \rho_j$ erfüllt die $j.$ \underline{negativ} beantwortete Orakelanfrage $\rho_j \in SAT$ \underline{nicht}.

            Es gibt also ein Polynom $q(n)$ sodass $x \in L(M) \Leftrightarrow \exists_{q(|x|)} y . L_1(x,y) \land \exists_{p(|x|)} \eta . L_2(y,\eta) \land \forall_{q(|x|)} \rho . L_3(y, \rho)$ \\
            wobei $L_1, L_2, L_3 \in \ComplexityClassP$

            \begin{itemize}
                \item 
                    $L_1(x,y) \Longleftrightarrow y \text{ ist akzeptierender Lauf von } M \text{ auf } x \text{ bis auf Orakelanfragen}$

                \item 
                    $L_2(y,\eta) \Longleftrightarrow  \text{ Die in } y \text{ positiv beantworteten Orakelanfragen sind } \rho_1 \dots \rho_k, \eta =| y_1 \dots y_k \text{ und } \eta_i \vDash \psi_i \text{ für } i = 1 \dots k$

                \item 
                    $L_3(y, \rho) \Longleftrightarrow \text{ Die in } y \text{ negativ beantworteten Orakelanfragen sind } \psi_1 \dots \psi_k, \rho = \rho_1 \dots \rho_k \text{ und } \rho \mp \psi_i \text{ für } i = 1 \dots k$

            \end{itemize}

    \end{itemize}

\end{beweis}



\begin{korollar}
    
    $L \in \Pi_2^\ComplexityClassP \Longleftrightarrow \\
    \exists \text{ Polynom } p \land L' \in \ComplexityClassP: x \in \Leftrightarrow \forall_{p(|x|)} y . \exists_{p(|x|)} z . (x,y,z) \in L'$ 

\end{korollar}


\begin{satz}
    
    Ist $L \in \Sigma_n^\ComplexityClassP$, so existiert ein Polynom $p(n)$ und $L' \in \ComplexityClassP$ sodass\\
     $x \in L \Leftrightarrow y_1 \forall_{p(|x|)} y_2 \exists_{p(|x|)} y_3 \dots   Q_{p(|x|)} y_n . (x, y_1, \dots y_n) \in L'$\\
    $n$ gerade: $Q = \forall$\\
    $n$ ungerade: $Q = \exists$

\end{satz}

Beweis durch Induktion über $n$.











\begin{satz}

    \definiere{Satz von Kamp-Lipton}

    Falls $SAT$ polynomiell große Schaltkreise hat, so kollabiert die PH auf der zweiten Stufe.\\
    Das heißt $\forall n \geq 2 : \Sigma_n^\ComplexityClassP = \Sigma_2^\ComplexityClassP$.


    Dass $SAT$ polynomielle Schaltkreise hat soll heißen: Es gibt ein Polynom $p(n)$ und für jedes $n \in \N$ einen boolschen Schaltkreis $C_n$ mit $n$ Inputs und Größe $\leq p(n)$ ($|C_n| \leq p(n)$).\\
    Für alle aussagenlogische Formeln $\phi$ mit $|\phi| = n$ gilt $\phi \in SAT \Leftrightarrow C(\phi) = TRUE$, $C(\phi)$ die Bitkodierung von $\phi$ an die $n$ Inputs von $C$ anlegen.
    
\end{satz}

Kurznotation: $SAT \in \ComplexityClassP / poly$

Der Satz von Kamp-Lipton sagt also $SAT \in \ComplexityClassP / poly \Rightarrow \text{ PH } = \Sigma_2^\ComplexityClassP$

Hilfsmittel: Selbstreduzierbarkeit von SAT\\
Ein Schaltkreis $C_n$ wie oben beschrieben kann so umgebaut werden in einem Schaltkreis $D_n$ polynomielle Größe, dass bei Antwort TRUE eine erfüllende Belegung zurückgeliefert wird.

Das heißt $D_n$ hat $n$ Ausgänge, die eine Belegung kodieren sollen. Spezifiere 
\begin{itemize}
    \item 
        $\phi \in SAT . D_n(\phi) (\eta, TRUE)$ mit $\eta \vDash \phi$
    \item 
        $\phi \notin SAT . D_n(\phi) (\_, FALSE)$
\end{itemize}
$D_n$ ruft $C_n$ insgesamt $m \leq n$ mal auf, wobei $m$ die Zahl der Variablen plus eins ist.

% Wir zeigen jetzt unter Zuhilfenahme von $(D_n)_n$, dass $\Pi_2^\ComplexityClassP = \Sigma_2^\ComplexityClassP $:
% \begin{itemize}

%     \item ``$\subseteq$'':

%         Sei $L \in \Pi_2^\ComplexityClassP_2$ und (nach Satz) $\forall_{p(|x|)} y . \exists_{p(|x|)} z . (x,y,z) \in L'$ ($p$ Polynom, $L' \in \ComplexityClassP$)

%         $x \in L \Longleftrightarrow \exists_{q(|x|)}  D . D \text{ ist selbstverifizierender SAT-Tester so wie } (D_n)_n, $ \\
%         und\\
%         $\forall_{p(|x|)} y . D(``\exists_{p(|x|)} z . (x,y,z) \in L' '')  =  (\_, TRUE)$\\
%         $\Leftrightarrow$\\
%         % $\forall_{poly} \phi \forall_{poly} \eta . D(\phi) = (\_, FALSE) \land \eta \mp \phi \\
%         % \lor $\
%         blablabla



% \end{itemize}





% chapter np_und_p (end)