\section{Weitere {\bfseries NP}-vollständige Probleme} \inhalta{9-15} \only
{\begin{frame} Es gibt eine Fülle von interessanten $NP$-vollständigen Problemen. In diesem Abschnitt sollen einige von ihnen vorgestellt werden. Am Schluss betrachten wir zwei $NP$-harte Probleme aus der Theorie der formalen Sprachen. Wie kann man von einem gegebenen Problem $L$ nachweisen, dass es tatsächlich $NP$-vollständig ist? Man muss dazu zwei Dinge zeigen: \begin{enumerate} \item dass es in $NP$ liegt. Dazu genügt es, eine nichtdeterministische Turingmaschine anzugeben, die das Problem in Polynomzeit löst, d.h. die die entsprechende Sprache $L$ erkennt und in Polynomzeit arbeitet. Für die meisten Probleme geht das mit der `Guess and Check'-Methode , d.h. mit einer Maschine, die ähnlich arbeitet wie die Maschine für das $SAT$-Problem: in einer ersten, nichtdeterministischen Phase wird zu einer Eingabe $w$ etwas (ein Lösungsvorschlag, ein Beweisversuch) geraten, und in einer zweiten, deterministischen Phase wird der geratene Lösungsvorschlag überprüft. Die Maschine kann natürlich nur dann eine `Lösung' raten, wenn eine existiert, d.h. wenn $w$ zu $L $ gehört. \item dass es $NP$-hart ist. Dazu genügt es, von einem als $NP$-hart bekannten Problem $L'$ nachzuweisen, dass es polynomial reduzierbar auf das Problem $L$ ist, d.h. dass $L'\leq_p L$ gilt. Es ist nämlich jedes Problem $L''$ aus $NP $ auf $L'$ polynomial reduzierbar, d.h. es gilt $L''\leq L'$. Da die polynomiale Reduzierbarkeitsrelation transitiv ist (Lemma \ref{transitive Reduktion}), folgt $L''\leq L$, also dass $L''$ auf $L $ polynomial reduzierbar ist. Da $L''$ beliebig aus $NP$ gewählt war, ist damit auch $L $ als $NP$-hart erkannt. \end{enumerate} \end{frame}} \only{\begin{frame} Nachweis der $NP$-Vollständigkeit eines Problems $L$ i.d.R. durch: \pause \begin{enumerate} \item Zeige $L\in NP$ durch Konstruktion einer nichtdeterministischen Turingmaschine, die $L$ erkennt und in Polynomzeit arbeitet. \pause\\[2ex] Meist: 'Guess and Check'-Methode\pause\begin{itemize} \item in nichtdeterministischer Phase 1: Rate Lösungsvorschlag\pause \item in deterministischen Phase 2: Überprüfe Lösungsvorschlag \end{itemize} \item \pause Zeige, dass $L$ $NP$-hart ist \pause\\ durch Beweis von $L'\leq_p L$ für bekanntes $NP$-hartes Problem $L'$ \pause \\[2ex] Für beliebiges $L''\in NP$ gilt dann $L''\leq_p L'\leq_p L$ \pause\\ und damit $L''\leq_p L$. \end{enumerate} \end{frame}} \begin{frame} \only
{ Wir werden nun die in die in dem folgenden Diagramm aufgeführten $NP$-vollständigen Probleme vorstellen und von einigen zeigen, dass sie tatsächlich $NP$-vollständig sind. Die Pfeile in dem Diagramm geben mögliche Reduktionen an, mit denen man zeigen kann, dass die Probleme $NP$-hart sind, da $SAT$ schon als $NP$-hart bekannt ist (Satz \ref{Satz von Cook}). Einige der Reduktionen werden wir durchführen. Die restlichen findet man in (Schöning: Theoretische Informatik --- kurzgefasst). } \only{Beispiele $NP$-vollständiger Probleme mit möglichen Reduktionen:} \[\multiinclude[graphics={width=25em}]{grafik/NPvoll1}\] \end{frame} \begin{frame} \only
{ Im Einzelnen handelt es sich um die folgenden Probleme (nach Schöning, S. 164-165): } \begin{theorem}[NP-vollständige Probleme]\pause $NP$-vollständig sind:\pause\vspace{1em} {\bfseries 3KNF-Sat}\pause \begin{itemize} \item {\emph gegeben:} \pause Eine Boolesche Formel $F$ in konjunktiver Normalform\pause\\ (Klauselform) mit höchstens $3$ Literalen pro Klausel.\pause \item \emph{gefragt:} \pause Ist $F$ erfüllbar? \end{itemize} \pause{\bfseries CLIQUE}\pause \begin{itemize} \item \emph{gegeben:} \pause Ein ungerichteter Graph $G=(V,E)$ \pause und\\ eine Zahl $k\in\nz$ \pause \item \emph{gefragt:} \pause Besitzt $G$ eine 'Clique' der Größe mindestens $k$? \end{itemize} \pause (Eine 'Clique' der Größe $k$ ist eine Menge $V'\subseteq V$ \\ mit $|V'|\geq k$ und $\{u,v\}\in E$ für alle $u,v\in V'$ mit $u\neq v$.) \end{theorem}\end{frame}\begin{frame}\begin{cont}{} {\bfseries KNOTENÜBERDECKUNG}\pause \begin{itemize} \item \emph{gegeben:} \pause Ein ungerichteter Graph $G=(V,E)$ und \\eine Zahl $k\in\nz$ \pause \item \emph{gefragt:} \pause Besitzt $G$ eine 'überdeckende Knotenmenge' der Größe höchstens $k$? \end{itemize} \pause (Eine 'Knotenüberdeckung' der Größe $k$ ist eine Menge $V'\subseteq V$ mit $|V'|\leq k$, so dass für alle $\{u,v\}\in E$ gilt: $u\in V'$ oder $v\in V'$.)\vspace{1em} \pause {\bfseries RUCKSACK} (oder {\bfseries SUBSET SUM}) \pause \begin{itemize} \item \emph{gegeben:} \pause Natürliche Zahlen $a_1, a_2,...,a_k,b\in \nz$ \pause \item \emph{gefragt:} \pause Gibt es eine Teilmenge $J\subseteq \{1,2,...,k\}$ mit \[\sum_{i\in J}a_i=b\] \end{itemize} \end{cont}\end{frame}\begin{frame}\begin{cont}{} {\bfseries PARTITION} \pause \begin{itemize} \item \emph{gegeben:} \pause Natürliche Zahlen $a_1, a_2,...,a_k\in \nz$ \pause \item \emph{gefragt:} \pause Gibt es eine Teilmenge $J\subseteq \{1,2,...,k\}$ mit \[\sum_{i\in J}a_i=\sum_{i\not\in J}a_i\] \end{itemize} \pause{\bfseries BIN PACKING} \begin{itemize} \item \emph{gegeben:} \pause Eine 'Behältergröße' $b\in\nz$, \pause die Anzahl $k\in\nz$ der Behälter, \pause Objekte $a_1,a_2,...,a_n\in\nz$. \pause \item \emph{gefragt:} \pause Können die Objekte so auf die $k$ Behälter verteilt werden, dass kein Behälter überläuft? \end{itemize} \pause(Gibt es eine Abbildung $f:\{1,...,n\}\rightarrow\{1,...,k\}$, \pause so dass für alle $j\in\{1,...,k\}$ gilt $\sum_{f(i)=j}a_i\leq b$?) \end{cont}\end{frame}\begin{frame}\begin{cont}{} {\bfseries GERICHTETER HAMILTON-KREIS}\pause \begin{itemize} \item \emph{gegeben:} \pause Ein gerichteter Graph $G=(V,E)$. \pause \item \emph{gefragt:} \pause Besitzt $G$ einen Hamilton-Kreis? \end{itemize} \pause (D.h. gibt es Permutation $\pi$ der Knotenindizes $(v_{\pi(1)},v_{\pi(2)},...,v_{\pi(n)})$, \pause so dass stets $(v_{\pi(i)},v_{\pi(i+1)})\in E$ und $(v_{\pi(n)},v_{\pi(1)})\in E$) \pause {\bfseries UNGERICHTETER HAMILTON-KREIS} \pause \begin{itemize} \item \emph{gegeben:} \pause Ein ungerichteter Graph $G=(V,E)$. \pause \item \emph{gefragt:} \pause Besitzt $G$ einen Hamilton-Kreis? \end{itemize} \pause (D.h. gibt es Permutation $\pi$ der Knotenindizes $(v_{\pi(1)},v_{\pi(2)},...,v_{\pi(n)})$, \pause so dass stets $\{v_{\pi(i)},v_{\pi(i+1)}\}\in E$ und $\{v_{\pi(n)},v_{\pi(1)}\}\in E$) \end{cont}\end{frame}\begin{frame}\begin{cont}{} {\bfseries TRAVELING SALESMAN}\pause \begin{itemize} \item \emph{gegeben:} \pause Eine $n\times n$-Matrix $(M_{i,j})$ von 'Entfernungen'\\ zwischen $n$ 'Städten' \pause und eine Zahl $k$.\pause \item \emph{gefragt:} \pause Gibt es Permutation $\pi$ (eine 'Rundreise'), so dass \[\sum_{i=1}^{n-1}M_{v_{\pi(i)},v_{\pi(i+1)}}+M_{v_{\pi(n)},v_{\pi(1)}}\leq k\] \end{itemize} \pause {\bfseries FÄRBBARKEIT}\pause \begin{itemize} \item \emph{gegeben:} \pause Ein ungerichteter Graph $G=(V,E)$ \pause \\und eine Zahl $k\in\nz$\pause \item \emph{gefragt:} \pause Gibt es eine Färbung der Knoten in $V$ \\ mit $k$ verschiedenen Farben, so dass keine \\zwei benachbarten Knoten in $G$ dieselbe Farbe haben. \end{itemize} \end{cont}\end{frame} \begin{frame} \only
{ Für jedes dieser Probleme ist der Nachweis, dass es in $NP$ liegt, leicht mit der Guess and Check-Methode zu führen. Dazu zeigt man, dass man bei jedem dieser Probleme auf eine Eingabe hin einen Vorschlag für eine Lösung in Polynomzeit raten und diesen Vorschlag in Polynomzeit verifizieren kann. In allen Fällen handelt es sich um arithmetische oder Graphenprobleme mit Summenbildungen. Daher ist dies für jedes Problem unmittelbar einsichtig. Wir beschränken uns daher jeweils auf die entsprechende Reduktion in dem Diagramm oben, um nachzuweisen, dass das jeweilige Problem $NP$-hart ist. } \only{ Mit Guess and Check: \pause Alle Probleme liegen in $NP$\pause Jetzt: Teile der Reduktionen...\pause } \begin{theorem} {\bfseries 3KNF-SAT} ist $NP$-vollständig. \end{theorem} \only
{ Zur Erinnerung: ein \emph{Literal} ist eine Variable oder eine negierte Variable. Eine \emph{Klausel} ist eine Disjunktion von Literalen. Eine aussagenlogische Formel ist in \emph{konjunktiver Normalform} ({\bfseries KNF}), wenn sie eine Konjunktion von Klauseln ist. Eine Formel ist in {\bfseries 3KNF}, wenn sie eine Konjunktion von Klauseln ist, von denen jede höchstens drei Literale enthält. Beweis: Wir müssen {\bfseries SAT} auf {\bfseries 3KNF-SAT} polynomial reduzieren. Ausgehend von einer beliebigen Booleschen Formel $F$ müssen wir dazu eine konjunktive Form $F'$ mit höchstens 3 Literalen pro Klausel angeben, so dass gilt \[ F\textrm{ erfüllbar }\Leftrightarrow F'\textrm{ erfüllbar }\] Das bedeutet nicht \"Aquivalenz im strengen Sinne, sondern Erfüllbarkeitsäquivalenz. Wir haben es hier also nicht mit einer allgemeinen Umrechnung in eine konjunktive Form zu tun, sondern nur mit einer Umformung, die lediglich die Erfüllbarkeit erhalten muss. } \only{ \begin{itemize} \item \pause \emph{Literal}: Variable oder negierte Variable\pause \item \emph{Klausel}: Disjunktion von Literalen\pause \item \emph{konjunktive Normalform} ({\bfseries KNF}): Konjunktion von Klauseln\pause \item {\bfseries 3KNF}: Konjunktion von Klauseln mit je höchstens drei Literalen \end{itemize} \pause Beweis durch Nachweis von {\bfseries SAT}$\leq_p${\bfseries 3KNF-SAT}\pause D.h.: Gegeben Formel $F$, \pause konstruiere 3KNF $F'$ mit \pause \[ F\textrm{ erfüllbar }\Leftrightarrow F'\textrm{ erfüllbar }\] \pause Achtung: \begin{itemize}\item $F'$ hat mehr Variablen als $F$\pause \item Daher nicht $F\Leftrightarrow F'$\pause \item Verlangt ist nur Erfüllbarkeitsäquivalenz. \end{itemize} } \end{frame} \only{\begin{frame} $F$ wird in mehreren Schritten umgeformt:\pause 1. Schritt: \pause Wende die de Morgan-Regeln an \pause und bringen alle Negationszeichen zu den Literalen:\pause \GLA\neg(F\wedge G) &\pause \textrm{ ersetzt durch }&\pause (\neg F\vee \neg G)\\ \pause \neg(F\vee G) &\pause \textrm{ ersetzt durch }&\pause (\neg F\wedge \neg G) \GLE \pause 2. Schritt: \pause Ersetze iterativ Teilformeln $(x \circ x')$ mit \emph{Literalen} $x$, $x'$ \pause durch neue Variablen $y$ \pause und ergänze jeweils durch Formel $[y\Leftrightarrow(x \circ x')]$ \pause (Tiefe der Formeln wird reduziert!),\pause z.B. \GLA(F\circ (x \vee x') \circ G) &\pause\textrm{ durch }&\pause (F\circ y\circ G)\wedge [y\Leftrightarrow(x \vee x')] \\ \pause(F\circ (x \wedge x') \circ G) &\pause\textrm{ durch }&\pause (F\circ y\circ G)\wedge [y\Leftrightarrow(x \wedge x')] \GLE \pause 3. Schritt: \pause Ersetze alle Teilformeln $y\Leftrightarrow(x \circ x')$ durch Klauseln:\pause \GLA y\Leftrightarrow(x \vee x') &\pause \textrm{ durch }&\pause (y\vee\neg x)\wedge(y\vee\neg x')\wedge(\neg y \vee x \vee x')\\\pause y\Leftrightarrow(x \wedge x') &\pause \textrm{ durch }&\pause (\neg y\vee x)\wedge(\neg y\vee x')\wedge( y \vee \neg x \vee\neg x')\GLE \end{frame}} \begin{frame} Beispiel:\pause \GLA F= \pause F_0 &\pause =&\pause \neg(\neg(x_1 \vee \neg x_3) \vee x_2)\\[0.5ex] \pause \textrm{Schritt 1: }\pause F_1 &\pause =&\pause ((x_1 \vee \neg x_3) \wedge \neg x_2 \\[0.5ex] \pause \textrm{Schritt 2: }\pause F_2 &\pause =&\pause (y_1\wedge \neg x_2)\\&&\pause \wedge (y_1\Leftrightarrow(x_1 \vee \neg x_3))\\[0.5ex] \pause F_3 &\pause =&\pause y_2\\&&\pause \wedge [y_2\Leftrightarrow (y_1\wedge \neg x_2)]\\&&\pause \wedge [y_1\Leftrightarrow(x_1 \vee \neg x_3)] \\ \pause\textrm{Schritt 3: }\pause F_4 &\pause =&\pause y_2 \\&&\pause \wedge(\neg y_2\vee y_1 )\wedge(\neg y_2\vee \neg x_2)\wedge( y_2 \vee \neg y_1 \vee x_2)\\&&\pause \wedge (y_1\vee\neg x_1)\wedge(y_1\vee x_3)\wedge(\neg y_1 \vee x_1 \vee\neg x_3)\GLE \pause Stets: $F_i$ erfüllbar $\Leftrightarrow $ $F_{i+1}$ erfüllbar, \pause damit: $F$ erfüllbar $\Leftrightarrow $ $F_4$ erfüllbar\pause Aufwand der Umformungen: Polynomial in der Länge von $F$\pause Anmerkung: Das entsprechende Problem {\bfseries 2KNF-SAT} mit je maximal zwei Literalen liegt bereits in $P$... \end{frame} \begin{frame} \begin{theorem} Das {\bfseries CLIQUE}-Problem ist $NP$-vollständig. \end{theorem} \pause Beweis: Zeige {\bfseries 3KNF-SAT} $\leq_p$ {\bfseries CLIQUE}\pause \only
{ Sei $F$ eine Formel in {\bfseries 3KNF}. Da man eine Klausel mit nur einem Literal $z$ durch die Klausel $(z\vee z \vee z)$ und eine Klausel $(y \vee z)$ mit nur zwei Literalen durch die Klausel $(y \vee z\vee z)$ ersetzen kann, können wir annehmen, dass $F$ genau drei Literale pro Klausel hat: $$F = (z_{11} \vee z_{12} \vee z_{13}) \wedge ... \wedge (z_{m1} \vee z_{m2} \vee z_{m3})$$ Dabei sind die $z_{jk}$ aus $\{x_1,..., x_n\} \cup \{\neg x_1,..., \neg x_n\}$. Der Formel $F $ wird nun ein Graph auf die folgende Weise zugeordnet: $G= (V, E)$, $V= \{(1, 1), (1, 2), (1, 3),..., (m, 1), (m, 2), (m, 3)\}$, $ E = \{~\{(i, p), (j, q)\} \mid i \neq j\wedge z_{ip}\neq \neg z_{jq}\}$ } \only{ Sei $F$ eine Formel in {\bfseries 3KNF}. \pause O.B.d.A.: Jede Klausel hat exakt 3 Literale, \pause ansonsten:\\ Ersetze $(z)$ durch $(z\vee z \vee z)$ \pause und $(y \vee z)$ durch $(y \vee z\vee z)$\pause Also o.B.d.A.: \pause $$F = (z_{11} \vee z_{12} \vee z_{13}) \wedge ... \wedge (z_{m1} \vee z_{m2} \vee z_{m3})$$ \pause mit $z_{jk}$ aus $\{x_1,..., x_n\} \cup \{\neg x_1,..., \neg x_n\}$. \pause Betrachte folgenden Graphen $G(V,E)$ zur Formel $F$:\pause \GLA V&=& \{(1, 1), (1, 2), (1, 3),..., (m, 1), (m, 2), (m, 3)\} \\\pause E &\pause =&\pause \{~\{(i, p), (j, q)\} \mid i \neq j\pause \wedge z_{ip}\neq \neg z_{jq}\} \GLE } \end{frame} \begin{frame} Anmerkung: Die Vervielfachung der Literale ist nur zur leichteren Formulierung notwendig...) Als Beispiele Graphen zu: \begin{itemize} \item $$(x\vee y)\wedge (\neg x \vee y) \wedge ( x\vee \neg y)$$ \item $$x\wedge y\wedge (\neg x\vee\neg y)$$ \end{itemize} \end{frame} \begin{frame} Au"serdem ordnen wir der Formel $F$ die Zahl $k:=m$ zu.\pause Dann ist $F$ durch eine Belegung erfüllbar\pause \begin{itemize} \item genau dann, wenn es in jeder Klausel ein Literal gibt, das den Wert $1$ erhält, \pause z.B. $z_{1p_1},...,z_{mp_m}$,\pause \item genau dann, wenn es Literale $z_{1p_1},...,z_{mp_m}$ gibt mit $z_{ip_i}\neq \neg z_{jp_j}$ für $i\neq j$\pause \item genau dann, wenn es Knoten $(1, p_1), (2, p_2),..., (m, p_m)$ in $G$ gibt, die paarweise verbunden sind,\pause \item genau dann, wenn es in $G$ eine Clique der Grö"se $k=m$ gibt. \end{itemize} \end{frame} \begin{frame} \begin{theorem} {\bfseries KNOTENÜBERDECKUNG} ist $NP$-vollständig. \end{theorem} \only
{ Beweis: Man kann {\bfseries CLIQUE} leicht nach {\bfseries KNOTENÜBERDECKUNG} reduzieren: Der Graph $G= (V, E)$ und die Zahl $k$ werden abgebildet auf den Komplementgraphen $G' = (V, V^2\setminus E)$ und die Zahl $|V|-k$. } \only{ \pause Beweis: Zeige {\bfseries CLIQUE} $\leq_p$ {\bfseries KNOTENÜBERDECKUNG}\pause Verwende Abbildung $$(G,k)\mapsto (G',k')$$ \pause mit $$G' = (V, V^2\setminus E),~~~~~k':= |V|-k$$ bei $G= (V, E)$ } \end{frame} \begin{frame} \begin{theorem}\label{RUCKSACK} {\bfseries RUCKSACK} ist $NP$-vollständig. \end{theorem} \only
{ Zum Beweis reduzieren wir {\bfseries 3KNF-SAT} auf {\bfseries RUCKSACK}. Sei $F$ eine Formel in {\bfseries 3KNF}. Wie oben können wir annehmen, dass jede Klausel in $F $ genau drei Literale enthält: $$F = (z_{11} \vee z_{12} \vee z_{13}) \wedge ... \wedge (z_{m1} \vee z_{m2} \vee z_{m3})$$ Dabei sind die $z_{jk}$ aus $\{x_1,..., x_n\} \cup \{\neg x_1,..., \neg x_n\}$. Wir müssen nun Zahlen $a_1,..., a_k$ und $b$ angeben, so dass die Summe der $a_i$ gerade $b$ ergibt. Die Zahl $b$ ist gegeben durch $4...41...1$ ($m$-mal die Zahl $4$, $n$-mal die $1$ im Dezimalsystem). } \only{ \pause Beweis: Zeige {\bfseries 3KNF-SAT} $\leq_p$ {\bfseries RUCKSACK}. \pause Sei $F$ Formel in {\bfseries 3KNF}. \pause O.B.d.A: jede Klausel in $F $ enthält genau drei Literale:\pause $$F = (z_{11} \vee z_{12} \vee z_{13}) \wedge ... \wedge (z_{m1} \vee z_{m2} \vee z_{m3})$$ mit $z_{jk}$ aus $\{x_1,..., x_n\} \cup \{\neg x_1,..., \neg x_n\}$. \pause Wähle $b=\underbrace{4...4}_m\underbrace{1...1}_n$ (im Dezimalsystem!)\pause Gesucht: Zahlen $a_1,..., a_k$... } \end{frame} \only
{\begin{frame} Die Menge $\{a_1,..., a_k\}$ der Zahlen $a_i$ setzt sich aus vier verschiedenen Klassen von Zahlen zusammen: Zahlen $v_1,..., v_n$, Zahlen $v_1',..., v_n'$, Zahlen $c_1,...,c_m$ und Zahlen $d_1,..., d_m$. Die Zahlen $v_k$ werden folgenderma"sen definiert. Geschrieben als Dezimalzahl wie die Zahl $b$ steht an der $i$-ten Position (von links) der Zahl $v_k$ die Anzahl des Vorkommens der Variablen $x_k$ in positiver Form in der Klausel $i$. Im hinteren Ziffernblock wird der Index $k$ der Variablen $(1...n)$ in der Stellencodierung angezeigt: die erste Stelle wird $1$ für $x_1$, die zweite für $x_2$ etc., die anderen bleiben $0$. Analog werden dann Zahlen $v_k'$ für das negative Vorkommen der Variablen $x_k$ in der Klausel $i$ definiert. Die Zahlen $c_j$ und $d_j$ für $j= 1,..,m$ sind analog aufgebaut und haben im ersten Ziffernblock an der $j-$ten Stelle einfach eine $1$ bzw. eine $2$. \end{frame}} \only{\begin{frame} Menge $\{a_1,..., a_k\}$ besteht aus vier Klassen von Zahlen:\pause \begin{itemize} \item Zahlen $v_1,..., v_n$ \pause mit $$v_j= n_1...n_m~~\underbrace{0...0}_{j-1}1 \underbrace{0...0}_{n-j-1}$$ \pause wobei $n_i$= Anzahl des Vorkommens der Variablen $x_i$ in Klausel $i$\pause \item Zahlen $v_1',..., v_n'$ \pause mit $$v_j'= n'_1...n'_m~~\underbrace{0...0}_{j-1}1 \underbrace{0...0}_{n-j-1}$$ \pause wobei $n'_i$= Anzahl des Vorkommens des Literals $\neg x_i$ in Klausel $i$\pause \item Zahlen $c_1,...,c_m$ \pause mit $$c_j=\underbrace{0...0}_{j-1}1\underbrace{0...0}_{m-j-1}~~\underbrace{0...0}_n$$ \item \pause Zahlen $d_1,..., d_m$ mit $$d_j=\underbrace{0...0}_{j-1} 2\underbrace{0...0}_{m-j-1}~~\underbrace{0...0}_n$$ \end{itemize} \end{frame}} \begin{frame} Beispiel: $$F= (x_1 \vee \neg x_3 \vee x_5) \wedge (\neg x_1 \vee x_4 \vee x_5) \wedge (\neg x_2 \vee \neg x_2 \vee \neg x_5)$$ \pause mit $m= 3$, $n= 5$ \pause und $$\begin{array}{|c||c|} \hline \begin{array}{c} v_1 = 100~10000 \\ v_2 = 000~01000 \\ v_3 = 000~00100 \\ v_4 = 010~00010 \\ v_5 = 110~00001 \end{array} &\pause \begin{array}{c} v_1' = 010~10000 \\ v_2' = 002~01000 \\ v_3' = 100~00100 \\ v_4' = 000~00010 \\ v_5' = 001~00001 \end{array}\\\hline \hline \pause \begin{array}{c} c_1 = 100~00000 \\ c_2 = 010~00000 \\ c_3 = 001~00000 \end{array}&\pause \begin{array}{c} d_1 = 200~00000 \\ d_2 = 020~00000 \\ d_3 = 002~00000 \end{array}\\\hline \end{array}$$ \end{frame} \only
{\begin{frame} Nun zeigen wir folgendes: Wenn $F$ eine erfüllende Belegung besitzt, so lässt sich eine Auswahl der Zahlen treffen, die sich zu $b $ aufsummiert. Dabei nehme man $v_k$ bzw. $v_k'$ in die Auswahl auf, falls $x_k= 1$ bzw. $x_k= 0$ in der Belegung gilt. Dazu beachte man, dass zu jedem Index nur $v_k$ oder $v_k'$, aber nicht beide auftreten können. Daher ergibt die Summe der letzten $n$ Ziffern immer genau $1..1$. Schauen wir nun die ersten $m$ Ziffern an. Sie spiegeln das Vorkommen von $x_k$ bzw. $\neg x_k$ in den $m$ Klauseln wider. In den einzelnen Ziffern summieren sie sich zu $1$, $2$ oder $3$ auf. Ergänzt man dies in geeigneter Weise mit $c_j$ und/oder $d_j$, so ergibt sich in jeder Ziffer gerade $4$. \end{frame}} \only{\begin{frame} Hat $F$ eine erfüllende Belegung, so betrachte folgende Liste $A$ von Zahlen aus $\{v_1,...,v_n,v'_1,...,v'_n,c_1,...,c_m,d_1,...,d_m\}$\pause \begin{itemize} \item Falls $x_k= 1$, so füge $v_k$ zu $A$\pause \item Falls $x_k= 0$, so füge $v'_k$ zu $A$\pause \item Summe der Zahlen bisher: \pause $z_1...z_m\underbrace{1...1}_n$ mit $1\leq z_i\leq 3$\pause \item Falls $z_i=1$ für $1\leq i\leq m$, \pause so füge $c_i$ und $d_i$ zu $A$\pause \item Falls $z_i=2$ für $1\leq i\leq m$, \pause so füge $d_i$ zu $A$\pause \item Falls $z_i=3$ für $1\leq i\leq m$, \pause so füge $c_i$ zu $A$\pause \end{itemize} \pause Damit $$\sum_{a\in A}a=b$$ \end{frame}} \only
{\begin{frame} Sei nun umgekehrt eine Auswahl von Zahlen getroffen derart, dass die Summe gerade $b$ ergibt. Dann muss diese Auswahl für jeden Index $k$ aus $\{1,\ldots n\}$ entweder $v_k$ oder $v_k'$ enthalten. Da man durch Summation von $c_j$ und $d_j$ allein auf höchstens den Wert 3 an der Stelle $j$ (von links) kommt, muss auch für jeden Index $j$ aus $\{1,\ldots,m\}$ (also jeden Index einer Klausel) mindestens eine Zahl $v_k$ oder $v_k'$ ausgewählt sein, so dass die Summe von $c_j$ und $d_j$ in der Ziffer $j$ zu $4$ ergänzt wird. Das zugehörige Literal muss dann in der Klausel auftreten. Also erhält man aus der Auswahl $v_k$ oder $v_k'$ eine erfüllende Belegung der Formel $F$. \end{frame}} \begin{frame}% Sei andererseits $$\sum_{a\in A}a=b=\underbrace{4...4}_m\underbrace{1...1}_n$$ \pause Mit $c_1+...+c_m+d_1+...+d_m=\underbrace{3...3}_m\underbrace{0...0}_n$ gilt\pause \begin{itemize} \item entweder $v_k$ in $A $ oder $v'_k$ in $A$ für $1\leq k\leq n$\pause \item $v_k$, $v'_k$ nicht beide gleichzeitig in $A$!\pause \item Summe der $v_k,v'_k$ in $A$: \pause $z_1...z_m\underbrace{1...1}_n$ mit $z_i\geq 0$ \end{itemize} \pause Also: $F$ erfüllt durch Belegung mit $$x_k=1\Leftrightarrow v_k\in A$$ \end{frame} \begin{frame} \begin{theorem} {\bfseries PARTITION} ist $NP$-vollständig. \end{theorem} \only
{ Es gibt eine elementare Reduktion von {\bfseries RUCKSACK} auf {\bfseries PARTITION}. Sei $(a_1,..., a_k, b)$ ein Rucksackproblem und $M= a_1 + ... + a_k$, dann bilden wir ab: $$(a_1,..., a_k, b) \mapsto (a_1,..., a_k, M - b + 1, b+ 1)$$ Ist die Indexmenge $I$ aus $\{1,...,k\}$ eine Lösung des Problems {\bfseries RUCKSACK}, so ist $I\cup \{k+ 1\}$ eine Lösung von {\bfseries PARTITION}, denn es gilt $$\sum_I a_i + M - b+ 1 = b + M - b+ 1 = M - b+ b + 1 = \sum_{CI} a_i+ b+ 1$$ Dabei bezeichnet $CI$ das Komplement von $I$. Gibt es andererseits eine Lösung $J$ von {\bfseries PARTITION}, so können die beiden neuen Indizes $k+1$ und $k+2$ nicht beide in $J $ oder beide im Komplement von $J$ liegen, da die Summe der Zahlen mit Indizes in dieser Menge dann automatisch mindestens $M - b + 1 + b + 1 = M + 2$ wäre, also grö"ser wäre als die Summe der Zahlen mit Indizes in der anderen Menge. Diejenige unter den beiden Indexmengen $J$ und `Komplement von $J$', die den Index $k+1$ enthält, ist ohne diesen Index eine Lösung von {\bfseries RUCKSACK}. } \only{\pause Beweis: Zeige {\bfseries RUCKSACK} $\leq_p$ {\bfseries PARTITION}\pause Zu Rucksackproblem $(a_1,..., a_k, b)$ \pause und $M= a_1 + ... + a_k$ \pause wähle $$(a_1,..., a_k, b) \mapsto (a_1,..., a_k, M - b + 1, b+ 1)$$ \pause Ist Indexmenge $I\subseteq \{1,...,k\}$ Lösung des Problems {\bfseries RUCKSACK},\pause \\ dann ist $I\cup \{k+ 1\}$ Lösung von {\bfseries PARTITION}:\pause $$\sum_I a_i + M - b+ 1 = b + M - b+ 1 = M - b+ b + 1 = \sum_{C(I)} a_i+ b+ 1$$ \pause Dabei bezeichnet $C(I)$ das Komplement von $I$. \pause Andererseits: Sei Lösung von {\bfseries PARTITION} gegeben\pause \begin{itemize} \item $M{-}b{+}1$ und $b{+}1$ nicht in gleicher Partition:\pause \\ \item ansonsten wäre Summe dieser Partition $\geq M+2$,\pause \\ aber Summe der restlichen Zahlen $\leq M$ \end{itemize} \pause Also: Partition, die $M{-}b{+}1$ enthält, liefert Lösung $I$ für {\bfseries RUCKSACK} } \end{frame} \begin{frame} \begin{theorem} {\bfseries BIN-PACKING} ist $NP$-vollständig. \end{theorem} \only
{ Es gibt eine sehr einfache Reduktion von {\bfseries PARTITION} auf {\bfseries BIN-PACKING}: $(a_1,..., a_k)$ sei dabei die Eingabe für {\bfseries PARTITION}. Falls $\sum_{1\leq i\leq k} a_i$ ungerade ist, kann es keine Lösung geben, dann wählen wir eine eine Eingabe für {\bfseries BIN-PACKING}, die keine Lösung hat. Ansonsten setzen wir die Behältergrö"se mit $b= \sum_{1\leq i\leq k}a_i/2$ an und wählen 2 Behälter und die Zahlen $(a_1,..., a_k)$. } \only{ \pause Beweis: Zeige {\bfseries PARTITION} $\leq_p$ {\bfseries BIN-PACKING}\pause Partitionierungsproblem $(a_1,..., a_k)$ sei gegeben.\pause Falls $\sum_{1\leq i\leq k} a_i$ ungerade ist:\pause \begin{itemize} \item wähle beliebige unlösbare Eingabe $w$ für {\bfseries BIN-PACKING} \pause \item weder $(a_1,..., a_k)\in$ {\bfseries PARTITION} noch $w\in$ {\bfseries BIN-PACKING} \end{itemize} \pause Falls $\sum_{1\leq i\leq k} a_i$ gerade ist:\pause \begin{itemize} \item Anzahl der Behälter $k:=2$\pause \item Behältergrö"se $b:= \sum_{1\leq i\leq k}a_i/2$ \pause \item Wähle Zahlen unverändert als $(a_1,..., a_k)$ \end{itemize} \pause Damit\\ $(a_1,..., a_k)\in${\bfseries PARTITION} $\Leftrightarrow ((a_1,..., a_k),2,b)\in$ {\bfseries BIN-PACKING} } \end{frame} \begin{frame} \only
{ Für die verbleibenden Reduktionen in dem Diagramm oben, mit denen man die folgenden vier Sätze beweist, sei auf Schöning verwiesen. } \begin{theorem} Das {\bfseries GERICHTETE HAMILTON-KREIS} Problem $GHK$ ist $NP$-vollständig. \end{theorem} \begin{theorem} Das {\bfseries UNGERICHTETE HAMILTON-KREIS} Problem $UHK$ ist $NP$-vollständig. \end{theorem} \begin{theorem} Das {\bfseries TRAVELING SALESMAN}-Problem $TSP$ ist $NP$-vollständig. \end{theorem} \begin{theorem} Das {\bfseries Färbbarkeits}problem ist $NP$-vollständig. \end{theorem} \only{ \pause Beweise: vgl. Buch von Schöning } \end{frame} \only
{\begin{frame} Zum Abschluss wollen wir noch einige Probleme untersuchen, die mit formalen Sprachen zu tun haben. \begin{theorem} Das Wortproblem für monotone Grammatiken ist $NP$-hart. \end{theorem} % % \pause Beweis: % \only
{ % Sei $L\in NP$ eine beliebige Sprache, sei $M$ eine nichtdeterministische, % polynomial zeitbeschränkte Turingmaschine, die $L$ erkennt. % % Sei $p$ ein Polynom, % das die Rechenzeit von $M$ beschränkt. Sei $x_1...x_n$ aus $E^*$ % eine Eingabe für $M$. Wir können au"serdem annehmen, % dass die Maschine vor dem Anhalten alle benutzten Felder mit Blanks beschreibt % und den Schreibkopf zum Ausgangspunkt zurückführt. % % Wir kommen auf den Beweis von Satz \ref{KS zu LBA} zurück. % Dort hatten wir gezeigt, dass man einen $LBA$ durch eine monotone Grammatik simulieren kann. % } % \only{ % \pause Sei $L\in NP$ beliebig.\pause % \begin{itemize} % \item $M$ sei nichtdeterministische Turingmaschine mit $L=L(M)$\pause % \item Sei $p$ ein Polynom, % das die Rechenzeit von $M$ beschränkt\pause % \item O.B.d.A. $M$ überschreibt vor dem Anhalten alle benutzten Felder mit Blanks\pause % \item O.B.d.A. $M$ setzt den Schreibkopf exakt zum Ausgangspunkt zurück % \end{itemize} % \pause Sei $x=x_1...x_n$ aus $E^*$ % eine Eingabe für $M$. \pause % % Vgl. Beweis von Satz \ref{KS zu LBA}: % % Jeder $LBA$ kann durch monotone Grammatik simuliert werden,\pause \\ % dabei Zustand $s$ und Symbol $a$ unter dem Kopf als ein Symbol $(s,a)$ % % % } % \end{frame} % % % % \only
{\begin{frame} % % Ebenso wie dort ordnen wir jetzt \"Ubergängen der Turingmaschine monotone Produktionen zu: % Enthält die Menge $\delta(s, a)$ das Tupel $(s', b, L)$, % so beschreiben wir dies durch die folgende monotone Produktion: % $$c(s, a) \rightarrow (s', c) b\textrm{ für alle }c\in A$$ % \"Ahnliches gilt für Rechtsbewegungen ( $(s, a) c\rightarrow b (s', c)$ % für alle $c$ aus $A$ ) und Stehenbleiben ( $(s, a)\rightarrow (s', b)$ ) des Kopfes. % So können wir \"Ubergänge auf der Turingmaschine in Ableitungen % in der Sprache mittels Grammatikproduktionen umsetzen. Wir ergänzen diese Produktionen % durch folgende Produktionen: $(s_f,\Box)\rightarrow \Box$ für Endzustände $s_f$ und % \[S \rightarrow\Box^{p(n)} (s_0, x_1)x_2,..., x_n\Box^{ p(n)-n}\] % Dann kann durch diese Regel das Startwort aus der Startkonfiguration % generiert werden, so dass die zulässige Bandbreite gerade ausgefüllt ist. % \end{frame}} % % % \only{\begin{frame} % Analog \"Ubergänge von $M$ durch monotone Produktionen simuliert: % \pause % % --- für Linksbewegungen $(s', b, L)\in\delta(s, a)$ verwende Produktionen % $$c(s, a) \rightarrow (s', c) b\textrm{ für alle }c\in A$$ % \pause --- für Rechtsbewegungen verwende % $$(s, a) c\rightarrow b (s', c) \textrm{ für alle }c\in A$$ % \pause --- bei Stehenbleiben des Kopfes verwende % $$(s, a)\rightarrow (s', b)$$ % \pause Zusätzlich Produktionen $(s_f,\Box)\rightarrow \Box$ \pause und % \[S \rightarrow\Box^{p(n)} (s_0, x_1)x_2,..., x_n\Box^{ p(n)-n}\] % \pause (Startwort passend zur Startkonfiguration von $M$, % mit genügend Platz)\pause % % $\Longrightarrow$ Grammatik $G_x$ zur Eingabe $x=x_1...x_n$ % \end{frame}} % % \only
{\begin{frame} % Die neue Grammatik nennen wir $G_x$. % % % Die Abbildung, die $x$ die monotone Grammatik $G_x$ und das Wort $\Box^{2p(n)}$ % zuordnet, ist in polynomialer Zeit berechenbar und vermittelt eine Reduktion von $L $ % auf das Wortproblem für monotone Grammatiken. Es gilt nämlich: % % $ x$ aus $L$ % $\Leftrightarrow$ $\Box^{p(n)} (s_0, x_1)x_2,..., x_n\Box^{ p(n)-n} % \vdash^* \Box^{p(n)}(s_f, \Box)\Box^{p(n)-1}$ in $M$ % % $\Leftrightarrow$ $S\rightarrow\Box^{p(n)} (s_0, x_1)x_2,..., x_n\Box^{ p(n)-n} % \rightarrow^* \Box^{p(n)}(s_f, \Box)\Box^{p(n)-1}$ in der Grammatik $G_x$ % % $\Leftrightarrow$ $\Box^{2p(n)}$ aus $L(G_x)$. % % \end{frame}} % % % \only{\begin{frame} % Betrachte Abbildung $x\mapsto (G_x,\Box^{2p(n)})$:\pause % \begin{itemize} % \item in polynomialer Zeit berechenbar\pause % \item vermittelt eine Reduktion von $L$ auf das Wortproblem für monotone Grammatiken % \end{itemize} % \GLA % &\pause x\in L\\ % &\pause \Longleftrightarrow\\ % &\pause \Box^{p(n)} (s_0, x_1)x_2,..., x_n\Box^{ p(n)-n} % \vdash^* \Box^{p(n)}(s_f, \Box)\Box^{p(n)-1}\textrm{ in }M % \\ % &\pause \Longleftrightarrow\\ % &\pause S\rightarrow\Box^{p(n)} (s_0, x_1)x_2,..., x_n\Box^{ p(n)-n} % \rightarrow^* \Box^{p(n)}(s_f, \Box)\Box^{p(n)-1}\textrm{ in }G_x % \\ % &\pause \Longleftrightarrow\\ % &\pause \Box^{2p(n)}\in L(G_x) % \GLE % % \end{frame}} % % % % % \only
{\begin{frame} Es sei angemerkt, dass nich bekannt ist, ob das Wortproblem für monotone Grammatiken in {\bfseries NP} liegt. Tatsächlich ist das Problem sogar {\bfseries PSPACE}-vollständig. Das hei"st, erstens ist es mit polynomialem Speicherplatz lösbar, und zweitens können alle mit polynomialem Speicherplatz lösbaren Problemen auf dieses Problem polynomial reduziert werden. Man kann leicht sehen, dass {\bfseries NP} in {\bfseries PSPACE} enthalten ist. Ob die Umkehrung gilt, ist unbekannt. Es wird vermutet, dass {\bfseries NP} eine echte Teilmenge von {\bfseries PSPACE} ist. \end{frame}} \only{\begin{frame} Zusammnhänge zwischen den Komplexitätsklassen und kontextsensitiven (d.h. monotonen) Grammatiken: \begin{theorem} Das Wortproblem für monotone Grammatiken ist $NP$-hart. \end{theorem} Achtung: \pause \begin{itemize} \item Wortproblem für monotone Grammatiken ist sogar {\bfseries PSPACE}-vollständig,\pause \item es ist also polynomialem Speicherplatz lösbar,\pause \item alle anderen mit polynomialem Speicherplatz lösbaren Probleme sind auf das Wortproblem reduzierbar\pause \item Bekannt ist: {\bfseries NP} $\subseteq$ {\bfseries PSPACE}\pause \item Vermutlich jedoch: {\bfseries NP} $\neq$ {\bfseries PSPACE} \end{itemize} \end{frame}} \begin{frame} \begin{theorem} Das Problem {\bfseries Regulär-Inäquivalenz}, für zwei reguläre Ausdrücke festzustellen, ob sie inäquivalent sind, d.h. ob die zugehörigen Sprachen nicht identisch sind, ist $NP$-hart. \pause \end{theorem} \only
{ Wir zeigen, dass {\bfseries 3KNF-SAT} auf dieses Problem polynomial reduzierbar ist. Sei $F=K_1 \wedge ...\wedge K_m$ eine Formel in konjunktiver Form. In ihr mögen die Variablen $x_1,x_2,...,x_n$ vorkommen. Wir konstruieren zwei reguläre Ausdrücke $\alpha$ und $\beta$ über dem Alphabet $\{0, 1\}$. Sei $\alpha = (\alpha_1 | \alpha_2 | ... | \alpha_m)$, wobei $\alpha_i= \gamma_{i,1}...\gamma_{i, n}$ ist mit \[ \gamma_{i,j}=\left\{\begin{array}{ll} 0 & \textrm{ falls }x_j\textrm{ in }K_i\textrm{ vorkommt}\\ 1 & \textrm{ falls }\neg x_j\textrm{ in }K_i\textrm{ vorkommt}\\ (0|1) & \textrm{ sonst} \end{array}\right.\] } \only{ Beweis: \pause Zeige {\bfseries 3KNF-SAT} $\leq_p$ {\bfseries Regulär-Inäquivalenz}\pause Sei $F=K_1 \wedge ...\wedge K_m$ eine KNF-Formel mit Variablen $x_1,x_2,...,x_n$\pause Konstruiere reguläre Ausdrücke $\alpha$ und $\beta$ über dem Alphabet $\{0, 1\}$:\pause $$\alpha := (\alpha_1 | \alpha_2 | ... | \alpha_m)$$ \pause wobei $\alpha_i= \gamma_{i,1}...\gamma_{i, n}$ ist mit \[ \gamma_{i,j}=\left\{\begin{array}{ll} 0 & \textrm{ falls }x_j\textrm{ in }K_i\textrm{ vorkommt}\\ 1 & \textrm{ falls }\neg x_j\textrm{ in }K_i\textrm{ vorkommt}\\ (0|1) & \textrm{ sonst} \end{array}\right.\] } \end{frame} \only
{\begin{frame} Nun bemerkt man leicht Folgendes: \begin{itemize} \item Eine Variablenbelegung $a_1,...,a_n$ erfüllt die Klausel $K_i$ genau dann nicht, wenn $a_1...a_n$ aus $L(\alpha_i)$. \item Eine Belegung $a_1,..., a_n$ erfüllt die Formel $F$ genau dann nicht, wenn sie eine der Klauseln nicht erfüllt, also genau dann, wenn $a_1...a_n$ aus $L(\alpha)$. \end{itemize} Also gibt es eine Belegung, die $F$ erfüllt genau dann, wenn $L(\alpha)$ nicht gleich $\{0, 1\}^n$ ist. Daher setzen wir $\beta = (0 | 1)(0 | 1)...(0 | 1)$ ($n$-mal), also $L(\beta) = \{0, 1\}^n$. Wir erhalten: $F$ ist erfüllbar genau dann, wenn $L(\alpha) \neq L(\beta)$. Die Abbildung $F \rightarrow (\alpha, \beta)$ ist also eine passende Reduktionsabbildung von {\bfseries 3KNF-SAT} auf das Inäquivalenzproblem. Wir hatten gesehen, das man zu einem regulären Ausdruck effektiv einen NEA konstruieren kann. Das geht sogar in polynomialer Zeit. Die Umformung in DEA's ist aber hart, so dass die Lösung des \"Aquivalenzproblems für DEA's in Polynomialzeit nichts hilft. \end{frame}} \only{\begin{frame} Sei $a_1,...,a_n$ eine Belegung der Variablen $x_1,...,x_n$:\pause \begin{itemize} \item $a_1,...,a_n$ erfüllt die Klausel $K_i$ genau dann \emph{nicht}, \pause \\wenn das Wort $a_1...a_n$ aus $L(\alpha_i)$ ist. \pause \item $a_1,..., a_n$ erfüllt die Formel $F$ genau dann \emph{nicht},\pause \\ wenn sie eine der Klauseln nicht erfüllt,\pause \\ also genau dann, wenn das Wort $a_1...a_n$ aus $L(\alpha)$ ist. \end{itemize} \pause Setze daher $\beta = \underbrace{(0 | 1)(0 | 1)...(0 | 1)}_n$, \pause also $L(\beta) = \{0, 1\}^n$. \pause Damit: $F$ ist erfüllbar genau dann, wenn $L(\alpha) \neq L(\beta)$.\pause $F \mapsto (\alpha, \beta)$ reduziert also {\bfseries 3KNF-SAT} auf {\bfseries Regulär-Inäquivalenz} \pause Anmerkung: \pause \begin{itemize} \item Umwandlung 'regulärer Ausdruck $\rightarrow$ NEA' in polynomialer Zeit \pause \item Äquivalenztest für DEA ebenfalls in polynomialer Zeit \pause \item Aber: Umwandlung 'NEA $\rightarrow$ DEA' ist zu zeitaufwendig... \end{itemize} \end{frame}} \begin{frame} $G_1=(V_1,E_1)$ und $G_2=(V_2,E_2)$ seien ungerichtete Graphen.\pause Eine Bijektion $p$ von $V_1$ nach $V_2$ heißt Isomorphismus zwischen $G_1$ und $G_2$, \pause falls gilt: $(v,w)\in E_1\Leftrightarrow (p(v),p(w))\in E_2$.\pause \begin{theorem}[Isomorphie von Graphen]\pause Betrachte folgende graphentheoretische Probleme:\pause\vspace{1em} {\bfseries GRAPH-ISOMORPHIE}\pause \begin{itemize} \item \emph{gegeben:} \pause Ungerichtete Graphen $G_1=(V_1,E_1)$, $G_2=(V_2,E_2)$ \pause \item \emph{gefragt:} \pause Sind $G_1$ und $G_2$ isomorph? \end{itemize} \pause {\bfseries SUBGRAPH-ISOMORPHIE}\pause \begin{itemize} \item \emph{gegeben:} \pause Ungerichtete Graphen $G_1=(V_1,E_1)$, $G_2=(V_2,E_2)$ \pause \item \emph{gefragt:} \pause Ist $G_2$ zu einem Subgraphen von $G_1$ isomorph, \pause d.h. gibt es $V_1'\subseteq V_1$, so dass $G_2$ und $(V_1', E_1\cap V_1'\times V_1')$ isomorph sind? \end{itemize} \pause Dabei gilt: \begin{itemize} \item {\bfseries SUBGRAPH-ISOMORPHIE} ist NP-vollständig.\pause \item {\bfseries GRAPH-ISOMORPHIE} $\in$ NP, \pause aber Vollständigkeit unbekannt! \end{itemize} \end{theorem}\end{frame} \begin{frame} \begin{itemize} \item Sowohl {\bfseries SUBGRAPH-ISOMORPHIE} als auch {\bfseries GRAPH-ISOMORPHIE} liegen offensichtlich in NP. \pause \item{\bfseries CLIQUE}$\leq_p$ {\bfseries SUBGRAPH-ISOMORPHIE} \pause über die Reduktion $$(G,k)\mapsto (G,C_k)$$ wobei $C_k$ der vollständige Graph mit $k$ Knoten ist\\ (d.h. die Clique der Größe $k$). \pause \item Vermutung: \begin{quote}{\bfseries GRAPH-ISOMORPHIE} weder NP-vollständig noch in P. \end{quote} \end{itemize} \pause Daher immerhin: \begin{itemize} \item Ist {\bfseries GRAPH-ISOMORPHIE} reduzierbar auf ein Problem $A$, \\ \pause so ist $A$ wahrscheinlich nicht in P... \end{itemize} \end{frame} \begin{frame} Wichtige Teilklasse von NP: \Fb{Constraint Satisfaction Probleme} (CSP). \pause Aufbau der Probleme: \pause \begin{itemize} \item \Fb{$n$ Variablen $x_1, . . . ,x_n$} \pause für Werte aus endlichem Grundbereich $D$; \pause Lösungsraum ist die Menge $D^n$. \pause \item \Fb{$m$ Constraints $C_1, . . . , C_m$}, \pause d.h. 0-1-wertige Funktionen auf $D^n$. \pause $C_j$ ist ``erfüllt'' für ein $(a_1, . . . , a_n)\in D^n$, \pause wenn $C_j(a_1, . . . , a_n) = 1$ \pause \item Wenn jedes $C_j$ nur von maximal $k$ Variablen abhängt, \pause hat das Problem die \Fb{Ordnung $k$}. \end{itemize} \pause Angabe der Constraints geeignet codiert (Formeln, Graphen, o.ä..) \pause dabei: Überprüfung eines einzelnen Constraints sehr schnell möglich \pause Aufgabe: Gibt es eine Wertebelegung $(a_1, . . . ,a_n)\in D^n$ für die Variablen, so dass alle Constraints erfüllt sind? \end{frame} \begin{frame} Beispiele: \begin{itemize} \item {\bf 3-KNF-SAT} ist ein CSP: \pause \begin{itemize} \item mit $D = \{0, 1\}$ \item mit Klauseln als Constraints \pause \item der Ordnung $3$ \end{itemize} \pause \item allgemein: $k$-KNF-SAT bei maximal $k$ Variablen pro Klausel als CSP mit $|D|=2$ und Ordnung $k$ \pause \item {\bf $k$-Färbbarkeit} ist CSP: \pause \begin{itemize} \item $D=\{1,...,k\}$ Menge der Farben \pause \item Constraints = Kanten, \pause\\ $C_{(u,v)}$ ist erfüllt, wenn $u$ und $v$ verschieden gefärbt sind \pause\\ (also Ordnung $=2$) \end{itemize} \end{itemize} \pause Generell: CSPs sind NP-vollständig, \pause wenn \begin{itemize} \item $|D|\geq 2$ und Ordnung $\geq 3 $ \pause oder \item $|D|\geq 3$ und Ordnung $\geq 2 $ \end{itemize} \pause Sonderfall:$|D|=2$ und Ordnung $=2 $, z.B. {\bf $2$-KNF-SAT} \end{frame} \begin{frame} \begin{theorem}[2-KNF-SAT]\pause Das folgende Problem liegt in P:\pause\vspace{1em} {\bfseries 2KNF-Sat}\pause \begin{itemize} \item {\emph gegeben:} \pause Eine Boolesche Formel $F$ in konjunktiver Normalform\pause\\ mit höchstens $2$ Literalen pro Klausel.\pause \item \emph{gefragt:} \pause Ist $F$ erfüllbar? \end{itemize} \end{theorem} \pause Beweisidee: \pause \begin{itemize} \item Gegeben 2-KNF-Formel $F$ mit Variablen $x_1,x_2,...,x_n$. \pause \item O.B.d.A: zwei Literale pro Klausel (statt $(a)$ verwende $(a\vee a)$ ) \pause \item Klausel $(a\vee b)$ entspricht Implikation $(\neg a \rightarrow b)$ \pause und $(\neg b \rightarrow a)$ \pause \item Betrachte gerichteten Graphen $G_F=(V,E)$ \pause mit Knotenmenge $V=\{x_1,...,x_n,\neg{x_1},...,\neg{x_n}\}$ \pause \item Zu $E$: Für Klausel $(a\vee b)$ verwende Kanten \pause $(\neg a,b)$ und $(\neg b,a)$ \pause \item Damit: Klausel mit einem Literal $(a)$ ergibt Einzelkante $(\neg a,a)$ \end{itemize} \end{frame} \begin{frame} Beispiel: Graph $G_F$ zur folgenden Formel $F$: \pause $$F=\underbrace{(x_1\vee x_2)}_{1}\wedge\underbrace{(\neg {x_1}\vee x_3)}_{2}\wedge\underbrace{(x_2\vee\neg{x_3})}_{3}\wedge\underbrace{(\neg{x_2})}_{4}$$ \setbeamercovered{invisible} \pause \[\includegraphics[width=.35\textwidth]{grafik/2SAT.pdf}\] \setbeamercovered{transparent=20} \pause $F$ ist nicht erfüllbar: \begin{tabular}{@{}lc@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c} in Formel $F$: & $x_2$ falsch & $\stackrel{1}{\leadsto}$ & $x_1$ wahr & $\stackrel{2}{\leadsto}$ & $x_3$ wahr & $\stackrel{3}{\leadsto}$ & $x_2$ wahr & $\stackrel{4}{\leadsto}$ & $x_2$ falsch \\ im Graphen:& $\neg x_2$ &$\longrightarrow$ & $x_1$ &$\longrightarrow$ & $x_3$ &$\longrightarrow$ & $x_2$ &$\longrightarrow$ & $\neg x_2$ \end{tabular} \pause Also: Nutze Erreichbarkeit im Graphen $G_F$! \end{frame} \begin{frame} Betrachte transitive Hülle $G^*_F=(V,E^*)$ des Graphen $G_F$, \pause\\ d.h. $(a,b)\in E^*$ $\Leftrightarrow$ es gibt in $E$ Pfad von $a$ nach $b$. \pause $E^*$ kann in polynomialer Zeit berechnet werden \pause\\ (z.B. mit Warshall-Algorithmus, kubische Komplexität in $n$) \pause \begin{lemma} Eine 2-KNF-formel $F$ ist genau dann erfüllbar, \pause wenn für kein $i$ \pause\\ in $G_F$ ein Kreis der Form $x_i\rightarrow \cdots\rightarrow \neg{x_i}\rightarrow\cdots\rightarrow x_i$ existiert, \pause\\ d.h. wenn in $G_F^*$ nie beide Kanten $(x_i,\neg x_i)$ und $(\neg x_i,x_i)$ existieren. \end{lemma} \pause Beweis von `$\Longrightarrow$': \pause $(a\vee b)$ entspricht Kanten $(\neg a, b),(\neg b, a)\in E$ \pause Bei einer erfüllenden Belegung von $F$ gilt damit \pause \begin{enumerate} \item Ist Literal $a$ wahr, \pause sind alle Literale $b$ wahr mit $(a,b)\in E^*$. \pause \item Ist Literal $b$ falsch, \pause sind alle Literale $a$ falsch mit $(a,b)\in E^*$. \pause \item Ist $(\neg a,a)\in E^*$ für Literal $a$, so muss $a$ wahr sein. \end{enumerate} \pause Damit direkt ``$F$ erfüllbar $\Rightarrow$ $\neg\exists$ Kreis''. \end{frame} \begin{frame} `$\Longleftarrow$': \pause Für die Rückrichtung definiere `Belegung' (mit $\{0,1\}$) wie folgt: \pause (1) Für alle Literale mit $(\neg a,a)\in E^*$ setze $a\mapsto1$ \pause (damit $\neg a\mapsto 0)$. \pause (2) dann ergänze für diese $a$: \pause \begin{itemize} \item Setze alle $b$ mit $(a,b)\in E^*$ auf $1$. \pause \item Setze alle $b$ mit $(b,\neg a)\in E^*$ auf $0$. \end{itemize} \pause (3) Solange noch nicht alle Literale einen Wahrheitswert haben: \pause \begin{itemize} \item Wähle beliebiges(!) noch nicht gesetztes Literal $a$, setze es auf $1$. \pause \item Setze wieder alle $b$ mit $(a,b)\in E^*$ auf $1$. \pause \item Setze wieder alle $b$ mit $(b,\neg a)\in E^*$ auf $0$. \end{itemize} \pause Gibt es keine Kanten $(x_i,\neg x_i)$ und $(\neg x_i,x_i)$ in $E^*$,\\ so ist die Belegung wohldefiniert \pause und erfüllt $F$: \pause\\ Nie folgt auf $1$ im Graphen $G$ eine $0$, d.h. alle Klauseln sind erfüllt. \end{frame} \only
{\begin{frame} Anmerkungen zu den $NP$-vollständigen Problemen: Viele von ihnen sind in der Praxis von gro"ser Bedeutung. Obwohl sie $NP$-vollständig sind und ein effizienter Algorithmus zu ihrer Lösung daher nach dem heutigen Stand der Dinge nicht bekannt ist, muss man diese Probleme doch in irgendeiner Form lösen. Wie kann man vorgehen? Einerseits gibt es manchmal deterministische Algorithmen, die im Mittel polynomiale Laufzeit haben, z.B. für das Hamiltonkreisproblem. Allerdings bezieht sich dieser Mittelwert dann auf eine angenommene Verteilung der möglichen Eingaben, bei der man dann sorgfältig überprüfen muss, ob sie realistisch ist. Andererseits geht es bei einigen Problemen, z.B. dem Traveling Salesman Problem, in der Praxis gar nicht darum, zu prüfen, ob es eine Reiseroute gibt, deren Kosten eine gewisse Grenze nicht überschreiten, sondern darum, eine möglichst günstige Reiseroute zu finden. Wenn man sich mit einer Reiseroute zufrieden gibt, die nicht optimal sein muss, sondern z.B. bis zu 50\% teurer als eine optimale Reiseroute sein darf, so gibt es unter gewissen weiteren Voraussetzungen einen deterministischen polynomialen Algorithmus, der so eine Route liefert. Allerdings gibt es auch Probleme, bei denen selbst eine derartige scheinbar leichtere Version noch $NP$-vollständig ist. \end{frame}} \only{\begin{frame} \Fb{ Anmerkungen zu $NP$-vollständigen Problemen:}\pause \begin{itemize} \item Viele $NP$-vollständige Probleme mit großer praktischer Bedeutung\pause \item Effiziente Algorithmen sind jedoch nicht bekannt...\pause \item daher: Versuche, Problematik zu umgehen... \end{itemize} \pause z.B. betrachte mittlere Laufzeit statt Worst-Case-Komplexität:\pause \begin{itemize} \item z.B. für Hamiltonkreise: \pause deterministische Algorithmen mit polynomialer mittlerer Laufzeit\pause \item Vorsicht: \pause Mittelwert gilt für gewisse Verteilung der Eingaben\pause \item falls bei Anwendung andere Verteilung: exponentielle Laufzeit.... \end{itemize} \pause z.B. statt exakter Lösung nur Approximation der Lösung gewünscht:\pause \begin{itemize} \item z.B. Traveling Salesman: \pause 'günstige' Route reicht oft\pause \item Route z.B. bis zu 50\% teurer als eine optimale Reiseroute \pause \\ (+ weitere Voraussetzungen):\pause \\ deterministischer polynomialer Algorithmus existiert! \end{itemize} \pause Allerdings: \pause \\Manchmal auch Lösungs-Approximationen noch $NP$-vollständig... \end{frame}}