\section{{\bfseries NP}-Vollständigkeit} \inhalta{9-15} \begin{frame} \only
{ 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
{ 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{ \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
{ 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{ 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
{ 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 { 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
{ 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{ \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
{ 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{ 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
{\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{\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
{ 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{ (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
{\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{\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
{ 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
{Die übliche (etwas weniger formale) Formulierung dieses Problems ist:} \only{ \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
{\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
{\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{\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
{ Wir geben nun die Variablen der Formel $F_y$ und ihre Bedeutung an:} \only{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
{ 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{ \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
{ 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{ 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
{ $U_2$ betrifft die Felder des Bandes, über denen der Kopf nicht steht und die sich nicht ändern dürfen. } \only{ \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
{\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{\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
{\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{\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
{\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{\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}}