\section{{\bfseries NP}-Vollständigkeit}
\inhalta{9-15}
\begin{frame}
\only<article>{
 Wir wollen nun die $NP$-vollständigen Sprachen einführen und untersuchen. 
 Dazu brauchen wir eine Polynomzeit-Version des Reduzierbarkeitsbegriffs, siehe Definition \ref{Reduzierbarkeit} 
}

\begin{definition}
 Seien $A$ und $B$
 Sprachen über einem Alphabet $E$. \pause

Dann hei"st $A$
 auf $B$  polynomial reduzierbar, \pause
 wenn es eine in Polynomzeit berechenbare Funktion $f:E^*\rightarrow E^*$ 
gibt, \pause\\
so dass für alle $w\in E^*$ gilt:\pause
     \[w\in A \Longleftrightarrow f(w)\in B\]
\pause Schreibweise: $A\leq_p B$ \pause
\end{definition}
\only<article>{

Man beachte, dass in Polynomzeit berechenbare Funktionen automatisch total sind.

Bemerkung: Die Definition kann leicht auf den Fall verschiedener Alphabete für $A$
und $B$ übertragen werden. 
}
\only<presentation>{
\begin{itemize}
\item $f\in FP$, \pause also $f$ total\pause
\item Falls $A$, $B$ über verschiedenen Alphabeten $E_A$, $E_B$: \pause\\ Wähle z.B: $E:=E_A\cup E_B$
\end{itemize}
}
\end{frame}


\begin{frame}
\begin{lemma}\label{Abschluss nach unten}
\begin{itemize}
\item
 Falls $A \leq_p B$ und $B\in P$, \pause so ist auch $A \in P$. \pause
\item
 Falls $A \leq_p B$ und $B\in NP$, \pause so ist auch $A \in NP$. 
\end{itemize}
\end{lemma}

\pause Beweis: \\ 
\only<article>{
 Wir nehmen an, dass $B$ aus $P$
 sei und dass $M_B$ eine Turingmaschine sei, die $B $
erkennt und in Zeit $q$ arbeitet. Dabei sei $q $
ein Polynom. Ferner werde die Reduktion von $A $
nach $B$ durch eine Funktion  $f$ und eine die Funktion $f$ 
in Zeit $p$ berechnende Turingmaschine $M_f$ vollzogen. 
Dabei sei $p$  ein Polynom. 

Wir schalten nun die Maschinen $M_f$ und $M_B$  hintereinander, 
d.h. auf ein Eingabewort $w $ wird erst $M_f$  angewendet 
und auf das Ergebnis  $f(w)$ dann $M_B$. 
Diese kombinierte Maschine erkennt aber gerade $A$.
}
\only<presentation>{
Sei $A\leq_p B\in P$ mit Reduktionsfunktion $f$:\pause
\begin{itemize}
\item $M_B$ sei Turingmaschine $M_B$ mit $L(M_B)=B$\pause
\item $M_B$ arbeite in Zeit $q$ für Polynom $q$\pause
\item $M_f$ berechne $f$\pause
\item $M_f$ arbeite in Zeit $p$ für Polynom $p$ 
\end{itemize}
\pause Betrachte folgende Maschine $M$:\pause
\begin{itemize}
\item Aus Eingabe $w$ berechnet $M$ zuerst $v:=f(w)$ \pause\\ durch Simulation von $M_f$\pause
\item $M$ testet, ob $v\in B$ \pause durch Simulation von $M_B$\pause 
\item $M$ akzeptiert $w$ genau dann, wenn $v$ dabei von $M_B$ akzeptiert wird
\end{itemize}
\pause Damit sofort $L(M)=A$
}

\end{frame}




\begin{frame}
\only<article>{
Ihr Zeitbedarf ist nach oben beschränkt durch  $p(|w|) + q(|f(w)|)$. 
Wir können das Polynom $q $ eventuell etwas vergrö"sern und monoton machen, 
indem wir alle negativen Koffezienten in $q $ durch ihren jeweiligen Betrag ersetzen. 
Das resultierende Polynom, es sei $q'$ genannt, hat die Eigenschaften 
$q(m) \leq q'(m)$ 
(es ist eine obere Schranke für $q$) und $q'(k) \leq q'(l)$ für $k\leq l$
  (es ist monoton). Also ist der Zeitbedarf der kombinierten Maschine wegen 
  $|f(w)| \leq p(|w|) + |w| $ nach oben beschränkt durch  
  $p(|w|) + q(|f(w)|) \leq p(|w|) + q'(p(|w|)+ |w|)$. 
  Der Zeitbedarf ist also durch ein Polynom beschränkt. 
Der additive Term $+|w|$ wird nur benötigt, um auch den Fall einzuschließen, dass die Eingabe $w$ gar nicht ganz gelesen wird, sondern z.B. nur nach links verlängert wird.

Der Fall $B$ aus $NP$
 wird analog behandelt. 
}
\only <presentation>{
Zeitbedarf von $M$:\pause  $$time_M(w)\leq p(|w|) + q(|f(w)|)$$
\pause O.B.d.A.: $q$ hat keine negativen Koeffizienten, \pause damit $q$ monoton\pause

Mit 
  $|f(w)| \leq p(|w|) + |w|$ also \pause\\ (dabei $...+|w|$ nur, weil $w$ evtl. nicht ganz gelesen wird!)
  $$time_M(w)\leq p(|w|) + q(|f(w)|) \leq\pause p(|w|) + q(p(|w|)+ |w|)$$ 
\pause d.h. polynomial in $|w|$\pause

Fall $A\leq_p B\in NP$: \pause analog \pause
}
\begin{lemma}\pause\label{transitive Reduktion}
 Die Relation $\leq_p$ ist transitiv, \pause d.h. aus $A\leq_p B\leq_p C$ folgt $A\leq_p C$.
\end{lemma}  
\only<article>{

 Dies beweist man ebenso wie Lemma \ref{Abschluss nach unten} durch 
 Hintereinanderschaltung zweier Maschinen, die in Polynomzeit Reduktionsfunktionen berechnen.


 Die Relation $\leq_p$
 ist übrigens auch reflexiv, aber nicht symmetrisch. 
}
\only<presentation>{
\pause Beweis: \pause Komposition der Reduktionen, \pause
Zeitschranke analog zu \ref{Abschluss nach unten} \pause

Anmerkung: $\leq_p$ ist reflexiv, \pause\\aber weder symmetrisch \pause
(d.h. $A\leq_p B\Rightarrow B\leq_p A$ gilt nicht)\pause\\ 
noch antisymmetrisch \pause(d.h. $(A\leq_p B\vee B\leq_p A)$ gilt nicht) 
}

\end{frame}

\begin{frame}

\begin{definition}
\begin{itemize}
\item Eine Sprache $L$
hei"st $NP$-hart, \pause \\ wenn \emph{alle} Sprachen aus $NP$
 auf sie polynomial reduzierbar sind.  \pause 

\item Eine Sprache $L$
hei"st $NP$-vollständig,  \pause \\
wenn sie aus $NP$
 ist und $NP$-hart ist. \pause 
\end{itemize}

\end{definition}  
\only<article>{
Nach dieser Definition sind die $NP$-vollständigen Probleme 
die schwierigsten unter den Problemen in $NP$. 
Der folgende Satz  besagt, dass man nur für ein einziges 
$NP-$vollständiges Problem einen Polynomzeitalgorithmus finden müsste, 
um nachzuweisen, dass $P$ und $NP$ gleich sind.}
\only<presentation>{
Damit:  $NP$-vollständige Probleme 
sind  schwierigste Probleme in $NP$!  \pause 
}
\begin{theorem}

$L$ sei $NP$-vollständig.  \pause Dann folgt:  \[ L\in P \Longleftrightarrow P=NP\] 
\end{theorem}

\end{frame}

\only<article>{\begin{frame}

Beweis:
Die Richtung `$\Leftarrow$' ist trivial. Wir zeigen `$\Rightarrow$'. 
Wir nehmen an,  $L$ sei aus $P$
und $NP$-vollständig. Da klar ist, dass $P$ in $NP$
enthalten ist, ist nur zu zeigen, dass $NP$ in $P$
enthalten ist. Sei $L'$ aus $NP $
beliebig. Da $L$  $NP$-hart ist, lässt sich $L'$
auf $L$ polynomial reduzieren. Daher ist nach Lemma \ref{Abschluss nach unten} auch $L'$
aus $P$. Da $L'$ beliebig war, folgt die Behauptung. 

Damit der Begriff der $NP$-Vollständigkeit überhaupt interessant ist, 
muss man nachweisen, dass es tatsächlich $NP$-vollständige Probleme gibt. 

Ein solches Problem ist das 'Erfüllbarkeitsproblem der Aussagenlogik'.
 
Dazu müssen wir beliebige aussagenlogische Formeln durch endliche Wörter 
über einem endlichen Alphabet codieren.

\end{frame}}

\only<presentation>{\begin{frame}
Beweis von '$\Leftarrow$':  \pause trivial \pause 

Beweis von '$\Rightarrow$':   \pause Sei $L\in P$ \pause 
und $NP$-vollständig.  \pause 


Betrachte beliebiges $L'\in NP$,  \pause damit $L'\leq_p L$. \pause 

Mit Lemma  \ref{Abschluss nach unten} also $L'\in P$ \pause 

Damit gilt $NP\subseteq P$;  \pause Inklusion $P\subseteq NP$ gilt nach 
 Definition
\end{frame}}


\begin{frame}

\only<article>{
Die Menge der \Fb{aussagenlogischen Formeln} ist ähnlich definiert wie die arithmetischen Formeln 
aus Kapitel \ref{arithmetische Formeln}, allerdings betrachten wir nur den logischen Teil und diesen auch nur ohne Quantoren. 
Wir beginnen daher mit Variablen, die Wahrheitswerte 
(hier $0$ für `falsch' und $1$ für `wahr') annehmen können:
Wir definieren entsprechend eine (kontextfreie) Sprache $\cal F$ wie folgt:}
\only<presentation>{
(kontextfreie) Sprache $\cal F$ der \Fb{aussagenlogischen Formeln}:\pause
}
\begin{itemize}
\item Jede Variable $x_i$ ist eine Formel (mit $i\in\nz$), \pause\\
 setze $V:=\{x_i\mid i\in\nz\}$\pause
\item Sind $F,G$ Formeln, \pause so auch $\neg F$, \pause $(F\wedge G)$ \pause und $(F\vee G)$
\end{itemize}

\pause Formeln können \Fb{ausgewertet} werden, \pause wenn den Variablen Werte zugewiesen werden:\pause
\begin{itemize}
\item Eine Belegung $\phi$ ist eine Abbildung $\phi:V\rightarrow \{0,1\}$\pause
\item $\phi$ kann auf Formeln erweitert werden \pause durch
\GLA \phi(\neg F)&\pause=&\pause 1-\phi( F)\\
\pause\phi(~(F \wedge G)~)&\pause=&\pause\min\{\phi(F),\phi(G)\} \\
\pause\phi(~(F \vee G)~)&\pause=&\pause\max\{\phi(F),\phi(G)\}
\GLE
\end{itemize}
\end{frame}



\only<article>{\begin{frame}

 Eine aussagenlogische Formel $F$ 
mit Variablen $x_i$ kann man durch ein Wort $code(F)$ über einem endlichen 
Alphabet $E=\{0,1,x,(,),\neg,\wedge,\vee\}$ codieren, indem man jede Variable $x_i$ durch das Wort $x~bin(i)$ codiert. 
Hat eine Formel die Länge $m$ und enthält $n$ Variablen, so hat das Wort $code(F)$ 
die Länge $m\log n$.

Im Folgenden werden wir in den Formeln $F$ den Variablen auch andere (aussagekräftigere) Namen geben. 
Wenn wir dann von $code(F)$ sprechen, ist folgendes gemeint:
Bestimme zunächst die in $F$ vorkommenden Variablen $v$,
ordne sie nach einer beliebigen Reihenfolge ($\pi(v)$ gebe dabei an, dass $v$ in dieser 
Reihenfolge an $\pi(v)$-ter Stelle kommt), benenne jede Variable $v$ zu $x_{\pi(v)}$ um und 
schreibe die enstandene Formel mit binär notierten Indizes auf.
Zum Beispiel würde $ \neg( \textrm{wichtige Variable} \vee (\textrm{andere Variable}\wedge \textrm{wichtige Variable}))$ notiert als $\neg( x1 \vee (x10\wedge x1))$.

Wir werden auch auf Klammern verzichten, wo dies ohne Mißverständnisse möglich ist, und Abkürzungen verwenden, etwa $\bigvee_{1\leq k\leq 4} x_k$ für $x_1\vee x_2\vee x_3\vee x_4$ mit Codierung
$((x1\vee x10)\vee (x11\vee x100))$, bzw.\ $x\rightarrow y$ als Umschreibung für $\neg x \vee y$.
\end{frame}}

\only<presentation>{\begin{frame}
Kodiere Variablen $x_i$ binär durch $x~bin(i)$, \pause dann gilt:  \pause 
\begin{itemize}
\item Für jede aussagenlogische Formel $F$ ist $code(F)$ Wort über  \pause \[E=\{0,1,x,(,),\neg,\wedge,\vee\}\]
\item  \pause  Hat $F$ Länge $m$  \pause und $n$ Variablen, \pause  dann gilt $|code(F)|\leq m\log n$. 
\end{itemize}
\pause Weitere Schreibweisen: \pause 
\begin{itemize}
\item aussagekräftigere Namen für Variablen sind erlaubt,  \pause etwa 
 $$F= \neg( \textrm{wichtige Variable} \vee (\textrm{andere Variable}\wedge \textrm{wichtige Variable}))$$ 
 \pause mit $code(F)= \neg( x1 \vee (x10\wedge x1))$ \pause 
\item Klammern dürfen fehlen  \pause (wo keine Mißverständnisse entstehen) \pause 
\item Abkürzungen sind erlaubt,  \pause  etwa   $\displaystyle\bigvee_{1\leq k\leq 4} x_k$   \pause
für $x_1\vee x_2\vee x_3\vee x_4$ \pause\\   \pause bzw.\ $x\rightarrow y$  \pause als Umschreibung für $\neg x \vee y$ \pause
\item aber stets: $code(F)$ als Wort über $E=\{0,1,x,(,),\neg,\wedge,\vee\}$
\end{itemize}
\end{frame}}

\begin{frame}
\begin{lemma}\label{eindeutig}

 Für jedes $m$ gibt es eine Formel $G$ der Länge $O(m^2)$\\
 mit den Variablen  $x_1,..., x_m$, \pause \\
 so dass $G$
 genau dann den Wahrheitswert $1$ erhält,\\
 wenn \emph{genau eine}
der Variablen mit $1$ belegt wird.   \pause 

\end{lemma}
  


 Beweis:  \pause Man wähle  
\[\displaystyle G(x_1,..., x_m) = \pause  (x_1\vee ... \vee x_m) \pause  \wedge (\bigwedge_{1 \leq j \leq m-1}~
\bigwedge_{ j+1 \leq l \leq m} \neg(x_j \wedge x_l)~)\]
\only<article>{ Die erste Teilformel wird genau dann wahr, wenn \emph{mindestens eine}
 Variable wahr ist. Die zweite Teilformel wird genau dann wahr, wenn \emph{höchstens eine}
 Variable wahr ist. D.h., die Formel $G$
 leistet das Gewünschte. Die Länge der Formel ist $O(m^2)$.

}

\end{frame}



\begin{frame}

\begin{definition}[Erfüllbarkeitsproblem der Aussagenlogik] \pause 
$SAT := \{code(F)$ aus $E^* \mid F$ erfüllbare Formel der Aussagenlogik$\}$ 
\end{definition}
\only<article>{Die übliche (etwas weniger formale) Formulierung dieses Problems ist:}
\only<presentation>{ \pause übliche, weniger formale Formulierung: \pause }
\begin{itemize}
\item gegeben:  \pause eine aussagenlogische Formel $F$ \pause 
\item gefragt:  \pause Ist $F$
erfüllbar,  \pause\\ d.h. gibt es eine Belegung der Variablen in $F$ mit $0$ und $1$,  \pause\\ so dass die Formel $F$
 den Wert $1$ erhält? \pause 
\end{itemize} 

\begin{theorem}[Cook] \pause 
 Das Erfüllbarkeitsproblem $SAT$ der Aussagenlogik ist $NP$-vollständig.\label{Satz von Cook}
\end{theorem}

\end{frame}


\only<article>{\begin{frame}

 Beweisskizze: \\ 
a) Wir zeigen zuerst, dass $SAT$ aus $NP $
ist. Wir müssen eine nichtdeterministische Turingmaschine beschreiben, die die Sprache $SAT$ erkennt und in polynomialer Zeit arbeitet. Sei eine aussagenlogische Formel $F$
in der Form $code(F)$ gegeben. Unsere Maschine soll in zwei Phasen arbeiten. 
In der ersten, nichtdeterministischen Phase rät die Maschine für jede in der Formel $F$
vorkommende Variable $x_i$ einen Wert $0$ oder $1$. Das geht sicher in Polynomzeit 
(d.h. in Zeit $O(p(n))$, wobei $p$ ein Polynom und $n$
die Länge des Wortes $code(F)$ ist). 

In der zweiten Phase, die tatsächlich sogar deterministisch ist, 
wertet die Maschine die Formel mit der geratenen Belegung der Variablen aus, 
bestimmt den Wert ($0$ oder $1$) der Formel und hält 
in einem Endzustand/in einem Nicht-Endzustand an, je nachdem, ob der Wert $1$ oder $0$ ist. 
Auch das geht sicher in Polynomzeit. 
Also arbeitet unsere Maschine insgesamt in Polynomzeit. 
Sie erkennt die Sprache $SAT$. Denn wenn die vorgegebene Formel $F$
erfüllbar ist, gibt es auch eine Rechnung der Maschine bei Eingabe von $code(F)$, 
bei der die Maschine den Wert $1$ errechnet, also das Wort akzeptiert. 
Wenn die vorgegebene Formel $F$ hingegen nicht erfüllbar ist, 
kann die Maschine auch keine erfüllende Belegung raten, 
und es gibt keine akzeptierende Berechnung. 

Bei Problemen aus $NP $ kann man oft eine nichtdeterministische Maschine angeben, 
die das Problem in zwei Phasen löst, einer nichtdeterministischen Ratephase 
und einer deterministischen Prüfphase ( \emph{guess and check} ).
\end{frame}}

\begin{frame} Beweisskizze zu $SAT\in NP$: \pause 

Eine aussagenlogische Formel $F$ sei gegeben durch $code(F)$ \pause 

Betrachte nichtdeterministische Turingmaschine $M$ wie folgt: \pause 
\begin{itemize}
\item Phase 1:  \pause $M$ rät einen Wert  $0$ oder $1$ für jede Variable $x_i$ von $F$. \pause \vsp
Aufwand:  \pause polynomial \pause 
(d.h. $\leq p(|code(F)|)$ für ein Polynom $p$)  \pause 
\item Phase 2:  \pause $M$ bestimmt Wert $z$ von $F$ bei diesen Werten für die $x_i$ \pause \\ 
Falls $z=1$, akzeptiert $M$ die Eingabe $code(F)$ \pause \\
Falls $z=0$, verwirft  $M$ die Eingabe $code(F)$ \pause 
\\[1ex]
Aufwand: \pause  wieder polynomial in $|code(F)|$ 
\end{itemize}
\pause Offensichtlich: $M$ arbeitet stets in Polynomzeit  \pause und \[code(F)\in SAT \Longleftrightarrow M\textrm{ kann akzeptieren}\]

 \pause Übliche Nachweismethode für $L\in NP$:  \pause \emph{guess and check} \pause 

--- rate nichtdeterministisch Lösungversuch \pause (Phase 1, guess) \pause 

--- überprüfe, ob  Lösungsversuch korrekt  \pause (Phase 2, check)
\end{frame}


\only<article>{\begin{frame}

 b) Nun ist noch zu zeigen, dass $SAT$ $NP$-hart ist. Sei dazu $L$
 ein beliebiges Problem aus $NP$ und $M$
 eine nichtdeterministische Turingmaschine, die die Sprache $L$
erkennt und in Polynomzeit arbeitet. Wir hatten angemerkt, 
dass man Mehrbandmaschinen durch Einbandmaschinen simulieren kann 
und dass sich der Zeitverbrauch dabei höchstens quadriert. 
Da es uns sowieso nur auf Polynomzeit ankommt, können wir daher annehmen, 
dass $M $ eine Einbandmaschine ist. Sei $p$ ein Polynom und 
eine obere Schranke für den Zeitverbrauch der Maschine. 
Au"serdem können wir benutzen, dass die Maschine einen 
einmal erreichten Endzustand nie mehr verlässt. 

Wir wollen nun zeigen, dass $L$ in Polynomzeit auf $SAT$ reduziert werden kann. 

Wir müssen also zu jeder Eingabe $y= y_1,...,y_n$ in polynomieller 
Zeit eine Boolesche Formel $F_y$ konstruieren, so dass die Eingabe $y$
genau dann aus $L$ ist, wenn $F_y$ erfüllbar ist. 

Die Formel wird so konstruiert, dass es genau dann eine erfüllende Belegung 
der Variablen mit $0$ oder $1$ gibt, wenn es bei der Eingabe $y_1,..., y_n$
eine akzeptierende Berechnung der Maschine $M$ gibt. 

Dazu beschreiben wir im Wesentlichen die Funktionen der Maschine durch 
Klauselformen in konjunktiver Form. 

Wir bezeichnen mit $A= \{a_1,..., a_l\}$ 
das Arbeitsalphabet, mit $S= \{s_0,...,s_k\}$ die Zustandsmenge und 
mit $S_f$ die Endzustandsmenge. 
\end{frame}}


\only<presentation>{\begin{frame}
Beweis, dass  $SAT$ $NP$-hart ist: \pause 

Sei dazu $L\in NP$  beliebig.  \pause 
\begin{itemize}
\item $M$ sei eine nichtdeterministische Turingmaschine mit $L=L(M)$ \pause 
\\ mit
Arbeitsalphabet $A= \{a_1,..., a_l\}$, \pause \\ 
Zustandsmenge $S= \{s_0,...,s_k\}$,  \pause Endzustandsmenge $S_f$ \pause 
\item $M$ arbeite in Polynomzeit \pause 
\item O.B.d.A.: $M$ ist Einbandmaschine \pause 
\item Polynom $p$ sei obere Schranke für den Zeitverbrauch von $M$ \pause 
\item Nutze u.a., dass $M$ im Endzustand nicht mehr weiterrechnet 
\end{itemize}

\pause Zeige: $L\leq_p SAT$, \pause  d.h.\\
zu jeder Eingabe $y= y_1,...,y_n$ (für $L$ gedacht, und mit $|y|=:n$) \pause\\
konstruiere (in Polynomzeit!) Boolesche Formel $F_y$  mit
\[F_y\textrm{ erfüllbar}\pause\Leftrightarrow  
M\textrm{ kann }y\textrm{ akzeptieren } \pause\Leftrightarrow  y\in L\]
\pause Also: Abbildung $y\mapsto F_y$ ist die gesuchte Reduktionsfunktion!
\end{frame}}







\begin{frame}
\only<article>{
Wir geben nun die Variablen der Formel $F_y$
und ihre Bedeutung an:}
\only<presentation>{Zunächst Auflistung der  Variablen von $F_y$:\pause}

\begin{tabular}{|c|c|c|}
\hline 
 Variable & Indizes & Bedeutung \\ \hline 
 \pause  $zust_{t, s}$
 &
  \pause \begin{tabular}[t]{c}
 $t= 0,...,p(n)$ \\
 \pause $s\in S$
\end{tabular}
 &
 \pause  \begin{tabular}[t]{c}
 $zust_{t, s}= 1 \Leftrightarrow$  \\\pause nach $t$
Schritten befindet \\\pause  sich $M$
im Zustand $s$
\end{tabular} 
 \\
 \hline 
\pause  $pos_{t,i}$ 
 &\pause 
 \begin{tabular}[t]{@{}c@{}}
 $t= 0,...,p(n)$   \\ \pause
$i= -p(n),..., p(n)$ 
\end{tabular}
 &
\pause  \begin{tabular}[t]{@{}c@{}}
 $pos_{t, i}= 1 \Leftrightarrow$   \\\pause Schreib-/Lesekopf von $M$
\\ \pause befindet sich nach $t$
Schritten \\\pause  auf Position $i$ 
\end{tabular}
 \\
 \hline 
 \pause $band_{t, i, a}$ 
 &\pause 
 \begin{tabular}[t]{@{}c@{}}
 $t= 0,..., p(n)$     \\ \pause
$i= -p(n),..., p(n)$    \\\pause 
$a\in A$ 
\end{tabular}
 &\pause 
 \begin{tabular}[t]{@{}c@{}}
 $band_{t, i, a} = 1 \Leftrightarrow$  \\\pause 
nach $t $ Schritten befindet sich \\\pause 
auf Position $i $
das Zeichen $a$
\end{tabular}
 \\
 \hline 
\end{tabular}

\only<article>{
 Hier ist zu beachten, dass die Variable $i $
bei $pos_{t, i}$ und $band_{t, i, a} $ von  $-p(n)$ bis $p(n)$ läuft. 
Das reicht, um den Bandinhalt der Maschine in einer innerhalb von $p(n)$ 
Rechenschritten erreichbaren Konfiguration zu beschreiben, 
da man mit dem Lese-Schreibkopf pro Rechenschritt höchstens 
eine Stelle nach links oder rechts wandern kann.
}
\only<presentation>{
 \pause $M$ rechnet nur $\leq p(n)$ Schritte  \pause \\$\Rightarrow$ $M$ bewegt den Kopf nur um $\leq p(n)$
Positionen
 \pause 

Also: $i$ mit  $-p(n)\leq i \leq p(n)$ reicht für alle vorkommenden
Positionen des Lese-Schreibkopfes!  
}
\end{frame}


\begin{frame}

\only<article>{
Nunmehr kommen wir auf die Struktur der Formel $F_y$
zu sprechen. $F_y$ setzt sich aus fünf durch $\wedge$ verbundene Teilformeln zusammen:

$R$ beschreibt gewisse Randbedingungen, $B_a$
die Anfangsbedingung, $U_1$, $U_2$ die \"Ubergangsbedingung und $B_e$
die Endbedingung. 


Wir beschreiben jetzt die Teilformeln im Einzelnen: 
}
\only<presentation>{ Struktur von $F_y$: \pause Fünf Teilformeln,  \pause durch $\wedge$ verbunden: \pause 

($R$:  Konsistenzbedingung, $B_a$ Anfangsbedingung, \\
$U_1$, $U_2$ \"Ubergangsbedingungen, $B_e$ Endbedingung) 
}     \[F_y \pause =R  \pause \wedge B_a  \pause \wedge U_1  \wedge U_2  \pause \wedge B_e  \]
\pause In $R$ wird ausgedrückt \pause (mit Formel $G$ aus Lemma \ref{eindeutig}),  \pause dass: \pause 
\begin{itemize}
\item Zu jedem Zeitpunkt $t$  gilt 
$zust_{t, s}= 1$ für genau ein $s$. \pause 
\item
Zu jedem Zeitpunkt $t$ gibt es genau eine Bandposition $i$, über der der Kopf steht:  \pause 
$pos_{t, i}= 1$.  \pause 
\item
Zu jedem Zeitpunkt $t$ und jeder Position $i$ gibt es genau ein $a$  \pause  mit $band_{t, i, a}= 1$.  
\end{itemize}
\pause Also: \pause 
\GLA R:= &\displaystyle\bigwedge_t &  \pause~ [~~
 G(zust_{t,s_0},..., zust_{t, s_k})
\\&& \pause ~~~~~\wedge~~  G(pos_{t, -p(n)},...,pos_{t, p(n)})
\\&& \pause ~~~~~ \wedge~~   \bigwedge_i G(band_{t, i, a_1},..., band_{t, i, a_l})~\pause ~]
\GLE
\end{frame}




\begin{frame}
 $B_a$
 beschreibt den Status der Variablen zum Startzeitpunkt $t= 0$:\pause
\GLA B_a&=& \pause zust_{0, s_0} \pause \wedge pos_{0, 1}\pause
 \wedge \bigwedge_{1 \leq j \leq n} band_{0, j, y_j}\\
&&\pause\wedge \bigwedge_{-p(n) \leq j \leq 0} band_{0, j, \Box}\pause
 \wedge \bigwedge_{n+1 \leq j\leq p(n)} band_{0, j, \Box}
\GLE

\pause $B_e$ prüft nach, ob im Zeitpunkt $p(n)$ ein Endzustand erreicht wird: \pause
\GLA  B_e
 = \bigvee_{s\textrm{  Endzustand}} zust_{p(n), s}\GLE

\only<article>{
$U_2$ betrifft die Felder des Bandes, über denen der Kopf nicht steht und die sich nicht ändern dürfen. }
\only<presentation>{
\pause $U_2$ betrifft die Felder des Bandes, über denen der Kopf nicht steht\pause\\
 (hier gibt es keine Änderungen!)\pause
}
\GLA
\displaystyle U_2 = \bigwedge_{t, i, a}
(~(\neg pos_{t, i}\wedge band_{t, i, a}) \rightarrow  band_{t+1, i, a}~)
\GLE


\end{frame}


\only<article>{\begin{frame}

$U_1$ betrifft die Bandpositionen, an denen sich der Kopf befindet 
 und beschreibt den nichtdeterministischen \"Ubergang vom Zeitpunkt $t$ zum Zeitpunkt $t{+}1$.
Dabei steht $b$ für -1 (L), 0 (N) oder 1 (R). 
\GLA&&\displaystyle U_1 = \bigwedge_{ t, s, i, a}[
(zust_{t, s}\wedge pos_{t, i}\wedge band_{t, i, a})  
\rightarrow \\&&
\bigvee_{s', a', b  \textrm{ mit } (s', a', b)\in \delta(s, a)}
(zust_{t+1, s'}\wedge pos_{t+1, i+b}\wedge band_{t+1, i, a'})]
\GLE
Ist dabei  $\delta(s, a)$ leer (für Endzustände $s\in S_f$ oder wenn $M$ in $s$ steckenbleibt),
so setzen wir in der obigen Formel $\delta(s, a):=(s,a,N)$, d.h. die Konfiguration bleibt dann beim Zeitpunkt  $t+1$ exakt wie beim Zeitpunkt $t$!

\end{frame}}

\only<presentation>{\begin{frame}

Zu $U_1$: \pause\begin{itemize}
\item betrifft die Bandpositionen, an denen sich der Kopf befindet \pause
\item   beschreibt den (nichtdeterministischen) \"Ubergang \pause\\ vom Zeitpunkt $t$ zum Zeitpunkt $t{+}1$.\pause
\item Dabei steht $b$ für -1 (L), 0 (N) oder 1 (R)
\end{itemize}

\GLA&&\pause\displaystyle U_1 = \pause \bigwedge_{ t, s, i, a}[ \pause 
(zust_{t, s}\wedge pos_{t, i}\wedge band_{t, i, a})
\rightarrow \\&& \pause
\bigvee_{s', a', b  \textrm{ mit } (s', a', b)\in \delta(s, a)}\pause
(zust_{t+1, s'}\wedge pos_{t+1, i+b}\wedge band_{t+1, i, a'})]
\GLE
\pause Ist dabei  $\delta(s, a)$ leer: \pause 
\begin{itemize}
\item d.h.\ für Endzustände $s\in S_f$  \pause oder wenn $M$ in $s$ steckenbleibt\pause
\item dann setze  $\delta(s, a):=(s,a,N)$\pause
\item d.h. Konfiguration bleibt dann bei  $t+1$ exakt wie bei $t$\pause
\item damit Akzeptanz/Nichtakzeptanz am Zeitpunkt $t=p(n)$ ablesbar!\pause\\ (vgl. $B_e$)
\end{itemize}
\end{frame}}


\only<article>{\begin{frame}

Nehmen wir an, dass $y = y_1...y_n$
in $L$
ist. Dann gibt es eine nichtdeterministische Rechnung der Länge $\leq p(n)$, 
die in einen Endzustand führt. Wenn alle Variablen der Formel $F_y$, 
die wir oben eingeführt haben, ihrer Bedeutung nach mit Wahrheitswerten belegt sind, 
so haben alle Teilformeln den Wert $1$. Damit ist $F_y$
erfüllbar. 

Ist umgekehrt $F_y$
durch eine gewisse Belegung ihrer Variablen erfüllt, so haben alle Teilformeln den Wert $1$. 
Insbesondere ist $R$ erfüllt. Daher können für jedes $t$ 
alle Variablenwerte von $zust_{t, s}$, $pos_{t, i}$
und $band_{t, i, a}$ sinnvoll als Konfiguration von $M$
interpretiert werden. Ferner erfüllt die Belegung $B_a$
und so haben wir für $t= 0$ eine aus den Variablen abzulesende 
gültige Startkonfiguration des Automaten $M$. Aus den erfüllten Belegungen von $U_1$ und 
$U_2$ können wir immer gültige \"Ubergänge von$ t$
nach $t{+}1$ ablesen, die eine nichtdeterministische Rechnung definieren. 
Schlie"slich hat auch $B_e$
den Wert $1$ mit der Konsequenz, dass die Rechnung in einen Endzustand gelangt. 
Damit liegt die Eingabe in der von der $M$ erkannten Sprache. 
\end{frame}}


\only<presentation>{\begin{frame}

Zeige $y\in L\Leftrightarrow$ $F_y$ ist  erfüllbar: \pause 

Beweis von '$\Rightarrow$': \pause Sei $y\in L$ \pause 
\begin{itemize}
\item
Also exisitiert Rechnung von $M$ auf $y$ mit Länge $\leq p(n)$, \\
die zu Endzustand führt.\pause 
\item
Definiere Belegung der Variablen in $F_y$ nach ihrer Bedeutung\pause 
\item
Damit: alle Teilformeln erhalten Wert $1$, \pause  d.h.\  $F_y$ ist  erfüllbar
\end{itemize}

\pause Beweis von '$\Leftarrow$': \pause Sei $F_y$ durch Belegung  erfüllt.\pause 
\begin{itemize}\item alle Teilformeln erhalten Wert $1$\pause 
\item
$R$ erfüllt:  \pause  Variablenwerte von $zust_{t, s}$, $pos_{t, i}$
und $band_{t, i, a}$ definieren Konfiguration $K_t$ von $M$ für jedes $0\leq t\leq p(n)$\pause 
\item
$B_a$ erfüllt: \pause  $K_0$ entspricht Startkonfiguration $I_M(y)$ \pause  \\(mit Zusatz-Leerzeichen)\pause 
\item
$U_1$, $U_2$ erfüllt: \pause $K_t\vdash K_{t+1}$ \pause oder Berechnung endet mit $K_t=K_{t+1}$\pause 
\item
$B_e$ erfüllt:  \pause Berechnung endet in Endzustand, \pause d.h. $y\in L(M)=L$
\end{itemize}
\end{frame}}






\only<article>{\begin{frame}

Nunmehr wollen wir noch die Komplexität der Berechnung der einzelnen Teilformeln notieren: \
Wir wollen die Anzahl der Variablenpositionen in den Teilformeln zählen. 
Die korrekt codierten Teilformeln sind dann nur unwesentlich länger 
(das hängt dann noch von der verwendeten Codierung ab). Die Zahl der Variablen in den 
Formeln $R$,  $U_1$ und $U_2$ ist in $O(p^2(n))$, die Variablenzahl in  
$B_a$ ist in $O(p(n))$ und die Variablenzahl in  
$B_e$ ist in $O(1)$. Daher ist die Länge von $R$ ebenso wie die Länge der Gesamtformel $F_y$
in $O(p^3(n))$. Die Länge ihrer Codierung $code(F_y)$ ist in $O(p^3(n) \log p(n))$. 
Die Codierung $code(F_y)$ der Formel $F_y$ wird nun bei der Eingabe von $y$
hingeschrieben. Dies geht in Zeit linear in der Länge von $code(F_y)$, 
also in Polynomzeit bezüglich der Länge $n$ des Eingabewortes  $y = y_1,..., y_n$. 

Wir haben damit gezeigt, dass das Problem $L$
polynomial auf $SAT$ reduzierbar ist. 

 In dem folgenden Kapitel werden wir weitere 
 $NP$-vollständige Probleme kennenlernen.

\end{frame}}



\only<presentation>{\begin{frame}

Komplexität der Bestimmung von $F_y$:\pause 


Insgesamt gibt es $O(p(n)^2)$ Variablen, \pause Länge der Teilformeln: \pause 
\begin{itemize}
\item $R$ hat Länge $O(p(n)^3)$ \pause  ($p(n)$-fach Formel $G$ mit $O(p(n))$ Variablen)\pause 
\item $U_1$, $U_2$ haben Länge $O(p(n)^2)$\pause 
\item $B_a$ hat Länge $O(p(n))$\pause 
\item $B_e$ hat konstante Länge $O(1)$
\end{itemize}
\pause Also: Länge von $code(F_y)$ ist in $O(p(n)^3 \log p(n))$\pause 

Aufwand zur Erstellung von $F_y$ aus $y$: \pause \begin{itemize}
\item Linear in  $|code(F_y)|$\pause \item d.h. polynomial in $n=|y|$
\end{itemize}

\end{frame}}
