\documentclass[11pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[utf8]{inputenc} \usepackage[margin=2.5cm]{geometry} \usepackage{amsmath,amssymb} \usepackage{tikz} \setlength{\parskip}{0.4em} \setlength{\parindent}{0pt} \setcounter{tocdepth}{1} \emergencystretch=1.5em % ---- Makros ---- \newcommand{\problem}[1]{\textsc{#1}} \newcommand{\redp}{\le_p} \newcommand{\NP}{\textsf{NP}} \newcommand{\true}{\textsf{wahr}} \newcommand{\false}{\textsf{falsch}} \tikzset{knoten/.style={circle,draw,thick,minimum size=6.5mm,inner sep=1pt}} % ---- Aufgabenkopf: Nummer + Titel, duenne Linie, keine Farbe ---- \newcounter{aufg} \newcommand{\aufg}[1]{\clearpage \stepcounter{aufg}% \addcontentsline{toc}{subsection}{\theaufg\ \ #1}% \noindent{\large\textbf{\theaufg\quad #1}}\par\nobreak \noindent\rule{\linewidth}{0.4pt}\par\medskip} \newcommand{\lsg}{\par\medskip\noindent\rule{\linewidth}{0.4pt}\par\smallskip \noindent\textbf{Lösung.}\par\smallskip} \title{\textbf{\Huge Übungsaufgaben}\\[0.4em] \large 71 Aufgaben nach Kompetenzliste\\ \normalsize \textit{Analyse von Algorithmen und Komplexität} -- CAU Kiel} \author{} \date{} \begin{document} \maketitle \thispagestyle{empty} \tableofcontents \clearpage \section{Anwendung} % ================================================================== \aufg{Greedy anwenden} Rucksack mit Kapazität $B = 10$; Gegenstände als $(p_i, w_i)$: \[ A = (10,6),\quad B = (7,5),\quad C = (6,4),\quad D = (3,3),\quad E = (4,2). \] Wenden Sie Greedy an und geben Sie den Lösungswert an. \emph{Hinweis:} Greedy sortiert absteigend nach Profitdichte $p_i/w_i$ und packt in dieser Reihenfolge jeden Gegenstand ein, der noch passt. \lsg \begin{itemize} \item Dichten $p_i/w_i$: $A\,1{,}67$, $B\,1{,}4$, $C\,1{,}5$, $D\,1{,}0$, $E\,2{,}0$. Sortiert: $E, A, C, B, D$. \item $E\,(w{=}2)$ einpacken -- Restkapazität $8$. \item $A\,(w{=}6)$ einpacken -- Restkapazität $2$. \item $C\,(w{=}4)$ passt nicht. \item $B\,(w{=}5)$ passt nicht. \item $D\,(w{=}3)$ passt nicht. \end{itemize} Auswahl $\{E, A\}$, Lösungswert $\mathrm{GA} = 4 + 10 = 14$. (Optimum wäre $\{A, C\}$ mit Wert $16$.) \hfill$\square$ % ================================================================== \aufg{ModifiedGreedy anwenden} Rucksack mit Kapazität $B = 8$; Gegenstände $(p_i, w_i)$: \[ a = (3,2),\quad b = (3,2),\quad c = (9,7),\quad d = (1,2). \] Wenden Sie ModifiedGreedy an. Wie ändert sich die Lösung gegenüber Greedy? \emph{Hinweis:} ModifiedGreedy gibt das Bessere aus Greedy-Lösung und profitreichstem Einzel-Gegenstand (der allein passt) aus. \lsg \begin{itemize} \item Dichten: $a\,1{,}5$, $b\,1{,}5$, $c\,1{,}29$, $d\,0{,}5$. Reihenfolge $a, b, c, d$. \item Greedy: $a$ rein (Rest $6$), $b$ rein (Rest $4$), $c\,(w{=}7)$ passt nicht, $d$ rein (Rest $2$). Greedy-Wert $\mathrm{GA} = 3+3+1 = 7$. \item Profitreichster Einzel-Gegenstand: $c$ mit Profit $9$ (und $w = 7 \le 8$). \item $\mathrm{MGA} = \max\{7,\ 9\} = 9$. \end{itemize} Die Lösung wechselt von der Greedy-Auswahl $\{a, b, d\}$ (Wert $7$) zum einzelnen Gegenstand $c$ (Wert $9$). \hfill$\square$ % ================================================================== \aufg{Sahni anwenden} Rucksack mit Kapazität $B = 11$; Gegenstände $(p_i, w_i)$: \[ A = (5,4),\quad B = (6,5),\quad C = (7,6),\quad D = (4,6). \] Wenden Sie Sahni mit $k = 2$ an. \emph{Hinweis:} Sahni probiert jede Vorauswahl aus höchstens $k$ Gegenständen, füllt sie jeweils mit Greedy auf und gibt die beste gefundene Lösung aus; das liefert Güte $1 + \frac1k$. \lsg \begin{itemize} \item Reines Greedy (Dichten $A\,1{,}25$, $B\,1{,}2$, $C\,1{,}17$, $D\,0{,}67$): $A$ rein (Rest $7$), $B$ rein (Rest $2$), $C$ und $D$ passen nicht -- Wert $11$. \item Vorauswahl $\{A, C\}$: Gewicht $4+6 = 10$, Greedy füllt nichts mehr (Rest $1$) -- Wert $12$. \item Vorauswahl $\{B, C\}$: Gewicht $5+6 = 11$, kein Platz mehr -- Wert $6 + 7 = 13$. \item Alle übrigen Vorauswahlen bleiben $\le 12$. \end{itemize} Beste Lösung: $\{B, C\}$ mit Wert $13$ (hier zugleich das Optimum). \hfill$\square$ % ================================================================== \aufg{ListScheduling anwenden} $m = 3$ Maschinen; Jobs in gegebener Reihenfolge $p = (3, 5, 2, 4, 1)$. Wenden Sie ListScheduling an. \emph{Hinweis:} Jeder Job kommt der Reihe nach auf die aktuell am wenigsten belastete Maschine; Lastvektor $(M_1, M_2, M_3)$. \lsg \begin{itemize} \item Start $(0,0,0)$. \item $3 \to M_1$: $(3,0,0)$. \item $5 \to M_2$: $(3,5,0)$. \item $2 \to M_3$: $(3,5,2)$. \item $4 \to M_3$ (kleinste Last $2$): $(3,5,6)$. \item $1 \to M_1$ (kleinste Last $3$): $(4,5,6)$. \end{itemize} Makespan $C_{\max} = 6$. \hfill$\square$ % ================================================================== \aufg{LPT anwenden} $m = 3$ Maschinen; Jobs $p = (4, 2, 6, 3, 5, 1)$. Wenden Sie LPT an. \emph{Hinweis:} LPT ist ListScheduling nach absteigender Sortierung der Bearbeitungszeiten. \lsg \begin{itemize} \item Absteigend sortiert: $6, 5, 4, 3, 2, 1$. \item $6 \to M_1$: $(6,0,0)$; \quad $5 \to M_2$: $(6,5,0)$; \quad $4 \to M_3$: $(6,5,4)$. \item $3 \to M_3$ (kleinste Last $4$): $(6,5,7)$. \item $2 \to M_2$ (kleinste Last $5$): $(6,7,7)$. \item $1 \to M_1$ (kleinste Last $6$): $(7,7,7)$. \end{itemize} Makespan $C_{\max} = 7$; wegen $\sum_j p_j = 21 = 3 \cdot 7$ ist das zugleich optimal. \hfill$\square$ % ================================================================== \aufg{RoundRobin anwenden} $m = 2$ Maschinen; Jobs $p = (3, 6, 1, 4)$. Wenden Sie RoundRobin an. \emph{Hinweis:} RoundRobin sortiert die Jobs absteigend und verteilt sie reihum: der $j$-te sortierte Job kommt auf Maschine $((j-1) \bmod m) + 1$. \lsg \begin{itemize} \item Absteigend sortiert: $6, 4, 3, 1$. \item Reihum bei $m = 2$: $6 \to M_1$, $4 \to M_2$, $3 \to M_1$, $1 \to M_2$. \item Lasten: $M_1 = 6 + 3 = 9$, \quad $M_2 = 4 + 1 = 5$. \end{itemize} Makespan $C_{\max} = 9$. (Optimal wäre $\{6,1\}$ / $\{4,3\}$ mit $\mathrm{OPT} = 7$.) \hfill$\square$ % ================================================================== \aufg{Parallel-Task-Scheduling anwenden} $m = 3$ Maschinen. Ein Job $(p_j, q_j)$ belegt $q_j$ Maschinen gleichzeitig für Zeit $p_j$. Jobs in Reihenfolge: \[ (2,1),\quad (2,2),\quad (1,3),\quad (3,1). \] Wenden Sie Parallel-Task-ListScheduling an. \emph{Hinweis:} Jeder Job startet zum frühesten Zeitpunkt, an dem $q_j$ Maschinen frei sind, auf den $q_j$ am wenigsten belasteten Maschinen. \lsg Lastvektor $(M_1, M_2, M_3)$ als Fertigstellungszeiten; Start $(0,0,0)$. \begin{itemize} \item $(2,1)$: eine Maschine $M_1$ (Last $0$), Start $0$, läuft $[0,2]$ -- $(2,0,0)$. \item $(2,2)$: zwei Maschinen $M_2, M_3$ (Last $0$), Start $0$, läuft $[0,2]$ -- $(2,2,2)$. \item $(1,3)$: alle drei Maschinen, frühester Start $= \max = 2$, läuft $[2,3]$ -- $(3,3,3)$. \item $(3,1)$: leerste Maschine $M_1$ (Last $3$), Start $3$, läuft $[3,6]$ -- $(6,3,3)$. \end{itemize} Makespan $C_{\max} = 6$. \hfill$\square$ % ================================================================== \aufg{TSP1 anwenden} Vollständiger, symmetrischer Graph $G$ auf $\{A,B,C,D,E\}$; die Dreiecksungleichung gilt für jede Kante. Wenden Sie $\Delta$TSP1 ab Startknoten $A$ an; geben Sie alle Zwischenschritte und die Tourlänge an. \begin{center} \begin{tikzpicture} \node[knoten] (A) at ( 90:2.1) {$A$}; \node[knoten] (B) at ( 18:2.1) {$B$}; \node[knoten] (C) at ( -54:2.1) {$C$}; \node[knoten] (D) at (-126:2.1) {$D$}; \node[knoten] (E) at ( 162:2.1) {$E$}; \draw (A) -- (B) node[fill=white,inner sep=1pt,font=\small,midway] {2}; \draw (B) -- (C) node[fill=white,inner sep=1pt,font=\small,midway] {1}; \draw (C) -- (D) node[fill=white,inner sep=1pt,font=\small,midway] {2}; \draw (D) -- (E) node[fill=white,inner sep=1pt,font=\small,midway] {1}; \draw (E) -- (A) node[fill=white,inner sep=1pt,font=\small,midway] {4}; \draw (A) -- (C) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {1}; \draw (A) -- (D) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {3}; \draw (B) -- (D) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {3}; \draw (B) -- (E) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {4}; \draw (C) -- (E) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {3}; \end{tikzpicture} \end{center} \emph{Hinweis ($\Delta$TSP1):} (1) MST $T$ berechnen; (2) alle MST-Kanten verdoppeln; (3) Eulerkreis ab Startknoten; (4) Abkürzen -- bereits besuchte Knoten überspringen. Güte $2$. \lsg \begin{itemize} \item[(1)] MST (Kruskal, aufsteigend): $A$--$C\,(1)$, $B$--$C\,(1)$, $D$--$E\,(1)$, $C$--$D\,(2)$; Gewicht $5$. Knoten $C$ hat Grad $3$. \item[(2)] Verdoppeln: alle Grade werden gerade, Multigraph-Gewicht $10$. \item[(3)] Eulerkreis ab $A$: $[A, C, B, C, D, E, D, C, A]$. \item[(4)] Abkürzen (besuchte Knoten überspringen): Tour $[A, C, B, D, E, A]$. \end{itemize} Tourlänge $= AC + CB + BD + DE + EA = 1 + 1 + 3 + 1 + 4 = 10$. \hfill$\square$ % ================================================================== \aufg{Christofides anwenden} Vollständiger, symmetrischer Graph $G$ auf $\{a,b,c,d\}$; die Dreiecksungleichung gilt für jede Kante. Wenden Sie Christofides ($\Delta$TSP2) ab Startknoten $a$ an; geben Sie alle Zwischenschritte und die Tourlänge an. \begin{center} \begin{tikzpicture} \node[knoten] (a) at (0,2.4) {$a$}; \node[knoten] (b) at (2.4,2.4) {$b$}; \node[knoten] (c) at (0,0) {$c$}; \node[knoten] (d) at (2.4,0) {$d$}; \draw (a) -- (b) node[fill=white,inner sep=1pt,font=\small,midway] {1}; \draw (a) -- (c) node[fill=white,inner sep=1pt,font=\small,midway] {2}; \draw (b) -- (d) node[fill=white,inner sep=1pt,font=\small,midway] {3}; \draw (c) -- (d) node[fill=white,inner sep=1pt,font=\small,midway] {3}; \draw (a) -- (d) node[fill=white,inner sep=1pt,font=\small,pos=0.3] {2}; \draw (b) -- (c) node[fill=white,inner sep=1pt,font=\small,pos=0.3] {3}; \end{tikzpicture} \end{center} \emph{Hinweis (Christofides):} (1) MST $T$ berechnen; (2) $X = $ Knoten mit ungeradem Grad in $T$; (3) minimales perfektes Matching $K$ auf $X$; (4) Eulerkreis in $T + K$; (5) Abkürzen. Güte $\frac32$. \lsg \begin{itemize} \item[(1)] MST (Kruskal): $a$--$b\,(1)$, $a$--$c\,(2)$, $a$--$d\,(2)$; Gewicht $5$ (Stern um $a$). \item[(2)] Grade im MST: $a{:}\,3$, $b{:}\,1$, $c{:}\,1$, $d{:}\,1$ -- alle ungerade, also $X = \{a,b,c,d\}$. \item[(3)] Minimales perfektes Matching auf $X$: Kandidaten $\{a b, c d\} = 1 + 3 = 4$, $\{a c, b d\} = 2 + 3 = 5$, $\{a d, b c\} = 2 + 3 = 5$. Wähle $K = \{\{a,b\}, \{c,d\}\}$, Kosten $4$. \item[(4)] Multigraph $T + K$ (Kante $a$--$b$ doppelt): alle Grade gerade. Eulerkreis ab $a$: $[a, b, a, c, d, a]$. \item[(5)] Abkürzen: Tour $[a, b, c, d, a]$. \end{itemize} Tourlänge $= ab + bc + cd + da = 1 + 3 + 3 + 2 = 9$. \hfill$\square$ % ================================================================== \aufg{Strip Packing: NFDH anwenden} Streifen der Breite $1$. Rechtecke als $(\text{Breite}, \text{Höhe})$: \[ r_1 = (0{,}6,\,3),\ r_2 = (0{,}5,\,2),\ r_3 = (0{,}5,\,2),\ r_4 = (0{,}4,\,1),\ r_5 = (0{,}3,\,1). \] Wenden Sie NFDH an und geben Sie die Gesamthöhe an. \emph{Hinweis:} NFDH sortiert nach Höhe absteigend und packt stufenweise von links; passt ein Rechteck nicht mehr, beginnt eine neue Stufe darüber. Die Stufenhöhe ist die Höhe ihres ersten (höchsten) Rechtecks. \lsg \begin{itemize} \item Sortiert nach Höhe: $r_1\,(3), r_2\,(2), r_3\,(2), r_4\,(1), r_5\,(1)$. \item Stufe 1: $r_1$ (Breite $0{,}6$, Höhe $3$). $r_2$: $0{,}6 + 0{,}5 = 1{,}1 > 1$ -- passt nicht. \item Stufe 2: $r_2$ (Höhe $2$), Breite $0{,}5$. $r_3$: $0{,}5 + 0{,}5 = 1{,}0 \le 1$ -- passt. $r_4$: $1{,}0 + 0{,}4 > 1$ -- passt nicht. \item Stufe 3: $r_4$ (Höhe $1$), Breite $0{,}4$. $r_5$: $0{,}4 + 0{,}3 = 0{,}7 \le 1$ -- passt. \end{itemize} Gesamthöhe $\mathrm{NFDH} = 3 + 2 + 1 = 6$. \begin{center} \begin{tikzpicture}[x=3.4cm,y=0.5cm] \draw[thin] (0,6.4) -- (0,0) -- (1,0) -- (1,6.4); \draw[fill=black!20] (0,0) rectangle (0.6,3); \node at (0.3,1.5) {$r_1$}; \draw[fill=black!12] (0,3) rectangle (0.5,5); \node at (0.25,4) {$r_2$}; \draw[fill=black!20] (0.5,3) rectangle (1.0,5); \node at (0.75,4) {$r_3$}; \draw[fill=black!12] (0,5) rectangle (0.4,6); \node at (0.2,5.5) {\small $r_4$}; \draw[fill=black!20] (0.4,5) rectangle (0.7,6); \node at (0.55,5.5) {\small $r_5$}; \draw[dashed,thin] (0,6) -- (1,6); \node[right,font=\small] at (1.03,6) {$\mathrm{NFDH} = 6$}; \node[below,font=\small] at (0.5,-0.4) {Breite $1$}; \end{tikzpicture} \end{center} Die Gesamtfläche ist $4{,}5$ (untere Schranke $\mathrm{OPT} \ge 4{,}5$); eine Packung der Höhe $5$ existiert. \hfill$\square$ % ================================================================== \clearpage \section{Vorlesungsbeweis} \aufg{$P \subseteq \NP$ zeigen} Zeigen Sie: $P \subseteq \NP$. \lsg Sei $L \in P$ beliebig. Dann entscheidet ein Algorithmus $A$ die Sprache $L$ in Zeit $O(n^d)$. \textbf{Konstruktion:} Fasse $A$ als Verifizierer auf durch $V(x,c) := A(x)$; das Zertifikat $c$ wird ignoriert. \textbf{Korrektheit:} Ist $x \in L$, so akzeptiert $V(x,c)$ für jedes $c$, etwa $c = \varepsilon$ -- ein akzeptiertes Zertifikat existiert. Ist $x \notin L$, so verwirft $V(x,c)$ für jedes $c$ -- kein Zertifikat wird akzeptiert. Also $L = \{x \mid \exists c:\ V(x,c) = 1\}$. \textbf{Laufzeit:} $V$ läuft wie $A$ in $O(n^d)$. Damit ist $V$ ein Verifizierer für $L$, und $L \in \NP$. Da $L$ beliebig war, folgt $P \subseteq \NP$. \hfill$\square$ \aufg{NDTM-Definition $\subseteq$ Verifizierer-Definition zeigen} Sei $L$ eine Sprache, die von einer NDTM $M$ in nichtdeterministischer Zeit $T$ (ein Polynom) entschieden wird. Zeigen Sie, dass ein polynomieller Verifizierer für $L$ existiert. \lsg Eingabe: Wort $x$ und als Zertifikat eine Folge $c$ von höchstens $T(|x|)$ nichtdeterministischen Entscheidungen von $M$. Der Verifizierer $V(x,c)$ arbeitet wie folgt: \begin{itemize} \item Simuliere $M$ auf $x$ deterministisch für höchstens $T(|x|)$ Schritte. \item Wähle an jeder Verzweigung den Übergang, den die Folge $c$ vorgibt. \item Akzeptiere, falls die Simulation akzeptierend hält; sonst verwirf. \end{itemize} \textbf{Korrektheit:} Ist $x \in L$, so hat $M$ einen akzeptierenden Rechenweg mit höchstens $T(|x|)$ Schritten; dessen Entscheidungsfolge ist ein Zertifikat, das $V$ akzeptiert. Ist $x \notin L$, so akzeptiert kein Rechenweg von $M$; jede Folge $c$ steuert die Simulation einen Rechenweg entlang, also verwirft $V$ jedes Zertifikat. \textbf{Laufzeit:} Höchstens $T(|x|)$ Simulationsschritte mit konstantem Aufwand -- $O(T(|x|))$; das Zertifikat hat Länge höchstens $T(|x|)$. Also existiert ein polynomieller Verifizierer für $L$. \hfill$\square$ \aufg{Verifizierer-Definition $\subseteq$ NDTM-Definition zeigen} Sei $L$ eine Sprache mit polynomiellem Verifizierer $M$ (Laufzeit $O(|x|^d)$): Für $x \in L$ existiert ein Zertifikat $c$ mit $M(x,c) = 1$, für $x \notin L$ akzeptiert $M$ kein Zertifikat. Zeigen Sie, dass eine NDTM $N$ die Sprache $L$ in Polynomialzeit entscheidet. \lsg Sei $p(|x|) = O(|x|^d)$ die Laufzeit von $M$. In $p(|x|)$ Schritten liest $M$ höchstens $p(|x|)$ Zeichen des Zertifikats. Die NDTM $N$ arbeitet bei Eingabe $x$ in zwei Phasen: \begin{itemize} \item \emph{Raten:} Schreibe mit nichtdeterministischen Entscheidungen einen String $u$ mit $|u| \le p(|x|)$ auf ein Arbeitsband. \item \emph{Verifizieren:} Simuliere $M$ auf $(x,u)$ und übernimm dessen Antwort. \end{itemize} \textbf{Korrektheit:} Ist $x \in L$, so existiert ein Zertifikat $c$ mit $M(x,c) = 1$; $M$ liest davon höchstens die ersten $p(|x|)$ Zeichen. Der Rechenweg, der genau diesen Anfang als $u$ rät, akzeptiert -- also akzeptiert $N$. Ist $x \notin L$, so verwirft $M$ jedes geratene $u$; alle Rechenwege verwerfen -- also verwirft $N$. \textbf{Laufzeit:} Phase~1 braucht $p(|x|)$ Rateschritte, Phase~2 läuft in $O(|x|^d)$ -- gesamt $O(|x|^d)$. Also entscheidet $N$ die Sprache $L$ in nichtdeterministischer Polynomialzeit. \hfill$\square$ \aufg{Transitivität von Polynomialzeitreduktionen zeigen} Zeigen Sie: Für Entscheidungsprobleme $L_1, L_2, L_3$ folgt aus $L_1 \redp L_2$ und $L_2 \redp L_3$ auch $L_1 \redp L_3$. \lsg Sei $R_1$ eine Reduktion $L_1 \redp L_2$ mit Laufzeit $O(n^a)$ und $R_2$ eine Reduktion $L_2 \redp L_3$ mit Laufzeit $O(n^b)$. Setze $R := R_2 \circ R_1$. \textbf{Korrektheit:} Für jede Eingabe $x$ gilt \[ x \in L_1 \iff R_1(x) \in L_2 \iff R_2(R_1(x)) \in L_3, \] also $x \in L_1 \iff R(x) \in L_3$. \textbf{Laufzeit:} Sei $|x| = n$. \begin{itemize} \item $R_1(x)$ braucht $O(n^a)$ Zeit; die Ausgabe hat damit Größe $O(n^a)$. \item $R_2$ auf dieser Ausgabe braucht $O((n^a)^b) = O(n^{ab})$ Zeit. \end{itemize} Somit ist $R$ eine Reduktion $L_1 \redp L_3$ mit Laufzeit $O(n^{ab})$. \hfill$\square$ \aufg{Vererbung der NP-Vollständigkeit zeigen} Zeigen Sie: Ist $L_0$ NP-vollständig, gilt $L_0 \redp L_1$ und ist $L_1 \in \NP$, so ist auch $L_1$ NP-vollständig. \emph{Hinweis:} Die Relation $\redp$ ist transitiv. \lsg $L_1 \in \NP$ gilt nach Voraussetzung. Zu zeigen bleibt, dass $L_1$ NP-schwer ist, also $L \redp L_1$ für jedes $L \in \NP$. Sei $L \in \NP$ beliebig. \begin{itemize} \item Da $L_0$ NP-vollständig ist, gilt $L \redp L_0$. \item Nach Voraussetzung gilt $L_0 \redp L_1$. \item Da $\redp$ transitiv ist, folgt $L \redp L_1$. \end{itemize} $L$ war beliebig, also reduziert jedes NP-Problem auf $L_1$ -- $L_1$ ist NP-schwer. Zusammen mit $L_1 \in \NP$ ist $L_1$ NP-vollständig. \hfill$\square$ \aufg{$L$ NP-vollständig: $L \in P \Leftrightarrow P = \NP$ zeigen} Sei $L$ eine NP-vollständige Sprache. Beweisen Sie: $L \in P$ genau dann, wenn $P = \NP$. \lsg \textbf{$\Leftarrow$:} Sei $P = \NP$. $L$ ist NP-vollständig, also $L \in \NP = P$. \textbf{$\Rightarrow$:} Sei $L \in P$. $P \subseteq \NP$ gilt stets. Zu zeigen bleibt $\NP \subseteq P$. Sei $L' \in \NP$ beliebig. Da $L$ NP-vollständig ist, gibt es eine Reduktion $f$ mit $L' \redp L$ und Laufzeit $O(n^a)$. Sei $A$ ein Algorithmus, der $L$ in Zeit $O(n^c)$ entscheidet. So entscheidet man $L'$: Berechne $f(x)$ und wende $A$ darauf an. Das ist korrekt, denn $x \in L' \iff f(x) \in L$. Die Ausgabe $f(x)$ hat Größe $O(n^a)$, also braucht $A$ darauf $O((n^a)^c) = O(n^{ac})$ Zeit. Also gilt $L' \in P$ für jedes $L' \in \NP$, und mit $P \subseteq \NP$ folgt $P = \NP$. \hfill$\square$ \clearpage \section{NP-Vollständigkeit} \aufg{NP-Vollständigkeit zeigen für $k$-Clique} Beweisen Sie, dass $k$-\problem{Clique} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie allgemeines \problem{SAT} (nicht 3-SAT). \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat $C \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Falls $|C| < k$, lehne ab. \item Prüfe für jedes Paar $\{u,v\} \subseteq C$, ob $\{u,v\} \in E$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert eine $k$-Clique, so ist sie ein akzeptiertes Zertifikat; sonst verletzt jedes Zertifikat eine Prüfung. Laufzeit: Größe zählen $O(|V|)$, alle Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt $k$-\problem{Clique} $\in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SAT} \redp k\text{-}\problem{Clique}. \] \problem{SAT} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $F = F_1 \wedge \dots \wedge F_m$ eine KNF-Formel; $y_{ij}$ sei das $j$-te Literal von Klausel $F_i$. Wir konstruieren daraus eine $k$-\problem{Clique}-Instanz durch: \begin{itemize} \item $V = \{[i,j] \mid y_{ij} \text{ ist Literal in } F_i\}$ \item $E = \{\{[i,j],[i',j']\} \mid i \ne i',\ y_{ij} \ne \neg y_{i'j'}\}$ \item $k = m$ \end{itemize} \textbf{Beweis hin:} \begin{itemize} \item Sei $\psi$ eine erfüllende Belegung von $F$. \item In jeder Klausel $F_i$ ist ein Literal wahr; wähle je eines, Knoten $[i,j_i]$. \item Sei $C = \{[i,j_i] \mid i \in [m]\}$; die $m$ Knoten stammen aus verschiedenen Klauseln. \item Zwei gewählte Literale sind beide unter $\psi$ wahr, widersprechen sich also nicht. \item Somit sind ihre Knoten durch eine Kante verbunden. \item Also ist $C$ eine $m$-Clique. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $C$ eine $m$-Clique in $G$. \item Knoten derselben Klausel sind nie verbunden, also enthält $C$ aus jeder Klausel genau einen Knoten. \item Die zugehörigen Literale widersprechen sich paarweise nicht (sonst fehlte eine Kante). \item Setze diese Literale wahr -- eine widerspruchsfreie Belegung. \item Sie erfüllt in jeder Klausel ein Literal. \item Also ist $F$ erfüllbar. \end{itemize} \textbf{Laufzeit:} Sei $L$ die Zahl der Literalvorkommen. Knoten anlegen $O(L)$, Kantenpaare prüfen $O(L^2)$ -- gesamt $O(L^2)$. Da $k$-\problem{Clique} $\in \NP$ und NP-schwer ist, folgt: $k$-\problem{Clique} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für 3-SAT} Beweisen Sie, dass \problem{3-SAT} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{SAT} auf \problem{3-SAT}. \lsg \textbf{$\in$ NP:} Eingabe: KNF-Formel $F$ mit Klauseln der Länge $\le 3$ und Zertifikat $\beta$ (eine Belegung der Variablen). Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Werte jede Klausel unter $\beta$ aus. \item Lehne ab, falls eine Klausel unerfüllt ist. \item Sonst akzeptiere. \end{itemize} Existiert eine erfüllende Belegung, so ist sie ein akzeptiertes Zertifikat; sonst scheitert jede. Laufzeit: alle Klauseln auswerten $O(|F|)$ -- gesamt $O(|F|)$. Also gilt $\problem{3-SAT} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SAT} \redp \problem{3-SAT}. \] \problem{SAT} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Ersetze jede Klausel $(y_1 \vee \dots \vee y_\ell)$ mit $\ell > 3$ durch die Kette \[ (y_1 \vee y_2 \vee x_1) \wedge (\neg x_1 \vee y_3 \vee x_2) \wedge \dots \wedge (\neg x_{\ell-3} \vee y_{\ell-1} \vee y_\ell) \] mit neuen Hilfsvariablen $x_1, \dots, x_{\ell-3}$ (pro Klausel eigene). Klauseln mit $\ell \le 3$ bleiben unverändert. \textbf{Beweis hin:} \begin{itemize} \item Sei die Originalklausel erfüllt, etwa $y_i$ wahr. \item Setze $x_1 = \dots = x_{i-2} = \true$ und $x_{i-1} = \dots = x_{\ell-3} = \false$. \item Die Kettenklauseln links von $y_i$ sind durch ihr positives $x$-Literal erfüllt. \item Die Klausel mit $y_i$ ist durch $y_i$ erfüllt. \item Die Kettenklauseln rechts sind durch ihr Literal $\neg x$ erfüllt. \item Also ist die ganze Kette erfüllt. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei die Kette erfüllt, aber angenommen, alle $y_i$ seien falsch. \item Dann erzwingt die erste Klausel $x_1 = \true$, die zweite $x_2 = \true$, induktiv $x_{\ell-3} = \true$. \item Dann ist die letzte Klausel $(\neg x_{\ell-3} \vee y_{\ell-1} \vee y_\ell)$ falsch -- Widerspruch. \item Also ist ein $y_i$ wahr und die Originalklausel erfüllt. \end{itemize} \textbf{Laufzeit:} Jede Klausel der Länge $\ell$ wird zu $\ell-2$ Klauseln -- gesamt $O(|F|)$. Da $\problem{3-SAT} \in \NP$ und NP-schwer ist, folgt: \problem{3-SAT} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für VertexCover} Beweisen Sie, dass \problem{VertexCover} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{Clique}. \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat $C \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Falls $|C| > k$, lehne ab. \item Prüfe für jede Kante $\{u,v\} \in E$, ob $u \in C$ oder $v \in C$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert ein Vertex Cover der Größe $\le k$, so ist es ein akzeptiertes Zertifikat; sonst bleibt eine Kante ungedeckt. Laufzeit: Größe zählen $O(|V|)$, Kanten prüfen $O(|E|)$ -- gesamt $O(|V| + |E|)$. Also gilt $\problem{VertexCover} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{Clique} \redp \problem{VertexCover}. \] \problem{Clique} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz mit $n = |V|$. Wir konstruieren daraus eine \problem{VertexCover}-Instanz $(G' = (V, E'),\, k')$ durch: \begin{itemize} \item $E' = \binom{V}{2} \setminus E$ \item $k' = n - k$ \end{itemize} Damit ist $G'$ der Komplementgraph von $G$. \textbf{Beweis hin:} \begin{itemize} \item Sei $C$ eine Clique in $G$ mit $|C| \ge k$. \item Setze $W = V \setminus C$; dann gilt $|W| \le n - k = k'$. \item Alle Kanten innerhalb $C$ liegen in $E$, also enthält $E'$ keine Kante mit beiden Endpunkten in $C$. \item Somit hat jede Kante von $G'$ einen Endpunkt in $W$. \item Also ist $W$ ein Vertex Cover von $G'$ mit $|W| \le k'$. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $W$ ein Vertex Cover von $G'$ mit $|W| \le k'$. \item Setze $C = V \setminus W$; dann gilt $|C| \ge n - k' = k$. \item Für $\{u,v\} \subseteq C$ gilt $u,v \notin W$, also $\{u,v\} \notin E'$. \item Da $E'$ genau die Nicht-Kanten von $G$ enthält, gilt $\{u,v\} \in E$. \item Also ist $C$ eine Clique in $G$ mit $|C| \ge k$. \end{itemize} \textbf{Laufzeit:} Alle Knotenpaare durchgehen und die Kanten invertieren -- $O(|V|^2)$. Da $\problem{VertexCover} \in \NP$ und NP-schwer ist, folgt: \problem{VertexCover} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für CliqueAndIndependentSet} \textbf{Problem \problem{CliqueAndIndependentSet}:} Gegeben ein Graph $G = (V,E)$ und $k$. Enthält $G$ zugleich eine Clique der Größe $k$ und ein Independent Set der Größe $k$ (eine Knotenmenge ohne Kanten untereinander)? Beweisen Sie, dass \problem{CliqueAndIndependentSet} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{Clique}. \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat $(C, I)$ mit $C, I \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Falls $|C| < k$ oder $|I| < k$, lehne ab. \item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$; lehne sonst ab. \item Prüfe für jedes Paar $\{x,y\} \subseteq I$, ob $\{x,y\} \notin E$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert beides, so ist $(C,I)$ ein akzeptiertes Zertifikat; sonst scheitert eine Prüfung. Laufzeit: alle Paare in $C$ und $I$ testen -- $O(|V|^2)$. Also gilt $\problem{CliqueAndIndependentSet} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{Clique} \redp \problem{CliqueAndIndependentSet}. \] \problem{Clique} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz, o.B.d.A.\ $k \ge 2$. Wir konstruieren daraus eine \problem{CliqueAndIndependentSet}-Instanz $(G' = (V', E'),\, k)$ durch: \begin{itemize} \item $V' = V \cup \{u_1, \dots, u_k\}$ mit $k$ neuen isolierten Knoten \item $E' = E$ \item $k$ bleibt unverändert \end{itemize} \textbf{Beweis hin:} \begin{itemize} \item Sei $C$ eine $k$-Clique in $G$. \item Da keine Kanten entfernt wurden, ist $C$ auch eine $k$-Clique in $G'$. \item Die Knoten $u_1, \dots, u_k$ sind isoliert, also paarweise nicht adjazent. \item Somit ist $\{u_1, \dots, u_k\}$ ein Independent Set der Größe $k$. \item Also enthält $G'$ eine $k$-Clique und ein Independent Set der Größe $k$. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $(G', k)$ eine Ja-Instanz; dann enthält $G'$ eine $k$-Clique $C'$. \item Wegen $k \ge 2$ hat jeder Knoten von $C'$ einen Nachbarn in $C'$. \item Die $u_1, \dots, u_k$ sind isoliert, liegen also nicht in $C'$. \item Somit gilt $C' \subseteq V$. \item Also ist $C'$ eine $k$-Clique in $G$. \end{itemize} \textbf{Laufzeit:} $k$ isolierte Knoten anhängen -- $O(k) \subseteq O(|V|)$. Da $\problem{CliqueAndIndependentSet} \in \NP$ und NP-schwer ist, folgt: \problem{CliqueAndIndependentSet} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für $k$-CliqueUniversal} \textbf{Problem $k$-\problem{CliqueUniversal}:} Gegeben ein Graph $G = (V,E)$ und $k$, wobei ein Knoten $u \in V$ mit allen anderen verbunden ist. Enthält $G$ eine Clique der Größe $\ge k$? Beweisen Sie, dass $k$-\problem{CliqueUniversal} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{Clique}. \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat $C \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Falls $|C| < k$, lehne ab. \item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert eine $k$-Clique, so ist sie ein akzeptiertes Zertifikat; sonst verletzt jedes Zertifikat eine Prüfung. Laufzeit: Größe zählen $O(|V|)$, alle Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt $k$-\problem{CliqueUniversal} $\in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{Clique} \redp k\text{-}\problem{CliqueUniversal}. \] \problem{Clique} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz. Wir konstruieren daraus eine $k$-\problem{CliqueUniversal}-Instanz $(\bar G = (\bar V, \bar E),\, \bar k)$ durch: \begin{itemize} \item $\bar V = V \cup \{u\}$ mit einem neuen Knoten $u$ \item $\bar E = E \cup \{\{u,v\} \mid v \in V\}$ \item $\bar k = k + 1$ \end{itemize} Der Knoten $u$ ist mit allen anderen verbunden, also ist $(\bar G, \bar k)$ eine gültige Instanz. \textbf{Beweis hin:} \begin{itemize} \item Sei $C$ eine Clique in $G$ mit $|C| \ge k$. \item $u$ ist mit allen Knoten von $C$ verbunden. \item Somit ist $C \cup \{u\}$ eine Clique in $\bar G$. \item Also gilt $|C \cup \{u\}| \ge k + 1 = \bar k$. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $\bar C$ eine Clique in $\bar G$ mit $|\bar C| \ge \bar k$. \item Setze $C = \bar C \setminus \{u\}$; dann gilt $|C| \ge \bar k - 1 = k$. \item Alle Kanten zwischen Knoten von $C$ liegen in $E$, denn neu sind nur Kanten an $u$. \item Also ist $C$ eine Clique in $G$ mit $|C| \ge k$. \end{itemize} \textbf{Laufzeit:} Einen Knoten und $|V|$ Kanten anlegen -- $O(|V|)$. Da $k$-\problem{CliqueUniversal} $\in \NP$ und NP-schwer ist, folgt: $k$-\problem{CliqueUniversal} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für Clique-Nomember} \textbf{Problem \problem{Clique-Nomember}:} Gegeben ein Graph $G = (V,E)$, ein Knoten $v \in V$ und $k$. Gibt es eine $k$-Clique, die $v$ \emph{nicht} enthält? Beweisen Sie, dass \problem{Clique-Nomember} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{Clique}. \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Knoten $v$, Zahl $k$ und Zertifikat $C \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Falls $|C| < k$ oder $v \in C$, lehne ab. \item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert eine $k$-Clique ohne $v$, so ist sie ein akzeptiertes Zertifikat; sonst scheitert eine Prüfung. Laufzeit: Größe und Ausschluss prüfen $O(|V|)$, alle Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt $\problem{Clique-Nomember} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{Clique} \redp \problem{Clique-Nomember}. \] \problem{Clique} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz. Wir konstruieren daraus eine \problem{Clique-Nomember}-Instanz $(G' = (V', E'),\, v,\, k)$ durch: \begin{itemize} \item $V' = V \cup \{v\}$ mit einem neuen, isolierten Knoten $v \notin V$ \item $E' = E$ \item $k$ bleibt unverändert \end{itemize} \textbf{Beweis hin:} \begin{itemize} \item Sei $C$ eine $k$-Clique in $G$. \item Da keine Kanten entfernt wurden, ist $C$ auch eine $k$-Clique in $G'$. \item Da $v \notin V$, gilt $v \notin C$. \item Also ist $C$ eine $k$-Clique in $G'$, die $v$ nicht enthält. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $C$ eine $k$-Clique in $G'$ mit $v \notin C$. \item Dann gilt $C \subseteq V$, denn $v$ ist der einzige neue Knoten. \item Alle Kanten zwischen Knoten von $C$ liegen in $E$. \item Also ist $C$ eine $k$-Clique in $G$. \end{itemize} \textbf{Laufzeit:} Graph kopieren und einen isolierten Knoten anhängen -- $O(|V| + |E|)$. Da $\problem{Clique-Nomember} \in \NP$ und NP-schwer ist, folgt: \problem{Clique-Nomember} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für $k$-COLOR-PRECOLORING} \textbf{Problem $k$-\problem{COLOR-PRECOLORING}:} Gegeben ein Graph $G = (V,E)$, eine Zahl $k$ und paarweise verschiedene Knoten $v_1, \dots, v_k \in V$. Gibt es eine Färbung $f: V \to [k]$ mit $f(u) \ne f(w)$ für alle $\{u,w\} \in E$ und $f(v_i) = i$ für alle $i$? Beweisen Sie, dass $k$-\problem{COLOR-PRECOLORING} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie $k$-\problem{Color}. \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$, Knoten $v_1, \dots, v_k$ und Zertifikat $f: V \to [k]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jedes $i \in [k]$, ob $f(v_i) = i$; lehne sonst ab. \item Prüfe für jede Kante $\{u,w\} \in E$, ob $f(u) \ne f(w)$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert eine gültige Färbung mit Vorgabe, so ist sie ein akzeptiertes Zertifikat; sonst scheitert eine Prüfung. Laufzeit: Vorgaben prüfen $O(k)$, Kanten prüfen $O(|E|)$ -- gesamt $O(k + |E|)$. Also gilt $k$-\problem{COLOR-PRECOLORING} $\in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ k\text{-}\problem{Color} \redp k\text{-}\problem{COLOR-PRECOLORING}. \] $k$-\problem{Color} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine $k$-\problem{Color}-Instanz. Wir konstruieren daraus eine $k$-\problem{COLOR-PRECOLORING}-Instanz $(G' = (V', E'),\, k,\, v_1, \dots, v_k)$ durch: \begin{itemize} \item $V' = V \cup \{v_1, \dots, v_k\}$ mit $k$ neuen Knoten \item $E' = E \cup \{\{v_i, v_j\} \mid i \ne j\}$; die $v_i$ bilden ein $K_k$, ohne Kante nach $V$ \item Vorgabe $f(v_i) = i$ \end{itemize} \textbf{Beweis hin:} \begin{itemize} \item Sei $f$ eine $k$-Färbung von $G$. \item Erweitere $f$ durch $f(v_i) = i$ für alle $i \in [k]$. \item Die $v_i$ sind nur untereinander verbunden und tragen paarweise verschiedene Farben. \item Somit ist $f$ eine gültige Färbung von $G'$ und erfüllt die Vorgabe. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $f$ eine gültige Färbung von $G'$ mit $f(v_i) = i$. \item Alle Kanten von $G$ liegen in $G'$. \item Also ist die Einschränkung von $f$ auf $V$ eine $k$-Färbung von $G$. \end{itemize} \textbf{Laufzeit:} Das $K_k$ anlegen -- $O(k^2)$. Da $k$-\problem{COLOR-PRECOLORING} $\in \NP$ und NP-schwer ist, folgt: Das Problem ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für FeedbackVertexSet} Beweisen Sie, dass \problem{FeedbackVertexSet} NP-vollständig ist: Gegeben ein \emph{gerichteter} Graph $G = (V,E)$ und $k$, gibt es $X \subseteq V$ mit $|X| \le k$, sodass $G \setminus X$ kreisfrei ist? \emph{Hinweis:} Reduzieren Sie \problem{VertexCover}. \lsg \textbf{$\in$ NP:} Eingabe: gerichteter Graph $G = (V,E)$, Zahl $k$ und Zertifikat $X \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Falls $|X| > k$, lehne ab. \item Prüfe per topologischer Sortierung, ob $G \setminus X$ kreisfrei ist; lehne bei einem Kreis ab. \item Sonst akzeptiere. \end{itemize} Existiert ein Feedback Vertex Set der Größe $\le k$, so ist es ein akzeptiertes Zertifikat; sonst scheitert eine Prüfung. Laufzeit: Größe zählen und topologisch sortieren -- $O(|V| + |E|)$. Also gilt $\problem{FeedbackVertexSet} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{VertexCover} \redp \problem{FeedbackVertexSet}. \] \problem{VertexCover} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{VertexCover}-Instanz. Wir konstruieren daraus eine \problem{FeedbackVertexSet}-Instanz $(G' = (V', E'),\, k')$ durch: \begin{itemize} \item $V' = V$ \item $E' = \{(u,v),\, (v,u) \mid \{u,v\} \in E\}$ \item $k' = k$ \end{itemize} So wird jede Kante zu zwei antiparallelen Bögen, also einem $2$-Kreis. \textbf{Beweis hin:} \begin{itemize} \item Sei $C$ ein Vertex Cover von $G$ mit $|C| \le k$. \item Dann ist $V \setminus C$ unabhängig in $G$. \item Also gibt es in $G'$ keinen Bogen zwischen zwei Knoten aus $V \setminus C$. \item Somit ist $G' \setminus C$ bogenlos, insbesondere kreisfrei. \item Also ist $C$ ein Feedback Vertex Set mit $|C| \le k' = k$. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $X$ ein Feedback Vertex Set von $G'$ mit $|X| \le k'$. \item Für jede Kante $\{u,v\} \in E$ bilden $(u,v),\, (v,u)$ einen $2$-Kreis in $G'$. \item $X$ zerstört jeden Kreis, trifft also diesen $2$-Kreis: $u \in X$ oder $v \in X$. \item Somit deckt $X$ jede Kante von $G$. \item Also ist $X$ ein Vertex Cover von $G$ mit $|X| \le k$. \end{itemize} \textbf{Laufzeit:} Pro Kante zwei Bögen anlegen -- $O(|E|)$. Da $\problem{FeedbackVertexSet} \in \NP$ und NP-schwer ist, folgt: \problem{FeedbackVertexSet} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für $\Delta$-Cover} \textbf{Problem $\Delta$-\problem{Cover}:} Gegeben ein Graph $G = (V,E)$ und $k$. Gibt es $C_\Delta \subseteq V$ mit $|C_\Delta| \le k$, sodass jedes Dreieck (3-Clique) von $G$ mindestens einen Knoten in $C_\Delta$ hat? Beweisen Sie, dass $\Delta$-\problem{Cover} NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{VertexCover}. \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat $C_\Delta \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Falls $|C_\Delta| > k$, lehne ab. \item Prüfe für jedes Tripel $\{a,b,c\} \subseteq V$ mit $\{a,b\}, \{b,c\}, \{a,c\} \in E$, ob es einen Knoten in $C_\Delta$ hat; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert eine Dreiecksüberdeckung der Größe $\le k$, so ist sie ein akzeptiertes Zertifikat; sonst bleibt ein Dreieck ungedeckt. Laufzeit: Größe zählen $O(|V|)$, alle Tripel prüfen $O(|V|^3)$ -- gesamt $O(|V|^3)$. Also gilt $\Delta$-\problem{Cover} $\in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{VertexCover} \redp \Delta\text{-}\problem{Cover}. \] \problem{VertexCover} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{VertexCover}-Instanz. Wir konstruieren daraus eine $\Delta$-\problem{Cover}-Instanz $(G' = (V', E'),\, k')$ durch: \begin{itemize} \item $V' = V \cup \{w_e \mid e \in E\}$ mit je einem neuen Knoten $w_e$ pro Kante \item $E' = E \cup \{\{w_e, u\}, \{w_e, v\} \mid e = \{u,v\} \in E\}$ \item $k' = k$ \end{itemize} So wird jede Kante $e = \{u,v\}$ zum Dreieck $\{u, v, w_e\}$. \textbf{Beweis hin:} \begin{itemize} \item Sei $C$ ein Vertex Cover von $G$ mit $|C| \le k$. \item Jeder neue Knoten $w_e$ hat genau die Nachbarn $u, v$; jedes Dreieck von $G'$ ist daher ein Gadget-Dreieck $\{u, v, w_e\}$ oder ein Dreieck $\{a,b,c\} \subseteq V$ aus $G$. \item Beim Gadget-Dreieck deckt $C$ die Kante $\{u,v\}$, enthält also $u$ oder $v$. \item Beim geerbten Dreieck deckt $C$ die Kante $\{a,b\}$, enthält also einen Eckknoten. \item Somit trifft $C$ jedes Dreieck von $G'$. \item Also ist $C$ eine Dreiecksüberdeckung mit $|C| \le k'$. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $C_\Delta$ eine Dreiecksüberdeckung von $G'$ mit $|C_\Delta| \le k'$. \item Enthält $C_\Delta$ ein $w_e$ mit $e = \{u,v\}$, ersetze es durch $u$; da $w_e$ nur im Dreieck $\{u,v,w_e\}$ liegt und dieses auch $u$ enthält, bleibt es eine Überdeckung und wird nicht größer. \item So entsteht $C \subseteq V$ mit $|C| \le k$, das jedes Dreieck von $G'$ trifft. \item Jede Kante $\{u,v\} \in E$ bildet mit $w_e$ das Dreieck $\{u, v, w_e\}$; $C$ trifft es, und da $w_e \notin C$, gilt $u \in C$ oder $v \in C$. \item Also ist $C$ ein Vertex Cover von $G$ mit $|C| \le k$. \end{itemize} \textbf{Laufzeit:} Pro Kante einen Knoten und zwei Kanten anlegen -- $O(|E|)$. Da $\Delta$-\problem{Cover} $\in \NP$ und NP-schwer ist, folgt: $\Delta$-\problem{Cover} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für 3-COLOR mit Minimalgrad 3} \textbf{Problem \problem{3-COLOR-Grad-3}:} \problem{3-COLOR}, eingeschränkt auf Graphen $G = (V,E)$ mit $\deg(v) \ge 3$ für alle $v \in V$. Ist $G$ mit $3$ Farben färbbar? Beweisen Sie, dass diese Variante NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{3-COLOR}. \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$ und Zertifikat $f: V \to \{1,2,3\}$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jeden Knoten $v$, ob $\deg(v) \ge 3$; lehne sonst ab. \item Prüfe für jede Kante $\{u,v\} \in E$, ob $f(u) \ne f(v)$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} Existiert eine $3$-Färbung der gültigen Instanz, so ist sie ein akzeptiertes Zertifikat; sonst hat eine Kante gleich gefärbte Endpunkte. Laufzeit: Gradprüfung $O(|V| + |E|)$, Kantenprüfung $O(|E|)$ -- gesamt $O(|V| + |E|)$. Also gilt die Grad-3-Variante $\in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{3-COLOR} \redp \problem{3-COLOR-Grad-3}. \] \problem{3-COLOR} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Benutze das Diamant-Gadget $D$ auf Knoten $p, q, r, s$ mit den Kanten $pq, pr, qr, qs, rs$ (ein $K_4$ ohne die Kante $\{p,s\}$; insbesondere sind $p, s$ nicht benachbart). Sei $G = (V,E)$ eine \problem{3-COLOR}-Instanz. Wir konstruieren $G'$ durch: \begin{itemize} \item Hänge an jeden Knoten $v \in V$ mit $\deg(v) < 3$ zwei eigene Kopien von $D$. \item Verbinde $v$ mit jeder Kopie über die Kanten $\{v, p\}$ und $\{v, s\}$. \end{itemize} Dann steigt $\deg(v)$ um $4$, und alle Gadget-Knoten haben Grad $3$ ($q, r$ über drei Gadget-Kanten, $p, s$ über zwei plus die Kante zu $v$); somit hat $G'$ Minimalgrad $3$. \textbf{Beweis hin:} \begin{itemize} \item Sei $f$ eine $3$-Färbung von $G$. \item Erweitere $f$ auf jedes an $v$ angehängte Gadget: Wähle eine Farbe $c \ne f(v)$ und setze $p = s = c$ (erlaubt, da $p, s$ nicht benachbart). \item $q$ und $r$ sind untereinander sowie zu $p$ und $s$ benachbart; da $p, s$ dieselbe Farbe $c$ tragen, bleiben für die Kante $qr$ die beiden anderen Farben -- färbe $q, r$ damit. \item Die Kanten $\{v,p\}, \{v,s\}$ sind gültig, da $c \ne f(v)$. \item Also ist $G'$ mit $3$ Farben färbbar. \end{itemize} \textbf{Beweis zurück:} \begin{itemize} \item Sei $f'$ eine $3$-Färbung von $G'$. \item Die Gadgets lassen die Originalkanten unverändert, also $E \subseteq E'$. \item Somit ist die Einschränkung von $f'$ auf $V$ eine $3$-Färbung von $G$. \end{itemize} \textbf{Laufzeit:} Pro untergradigem Knoten zwei Gadgets konstanter Größe anlegen -- $O(|V|)$. Da die Grad-3-Variante $\in \NP$ und NP-schwer ist, folgt: \problem{3-COLOR} mit Minimalgrad $3$ ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für HamiltonianPath} \textbf{Problem \problem{HamiltonianPath}:} Gegeben ein ungerichteter Graph $G = (V,E)$. Entscheide: Gibt es einen Pfad, der jeden Knoten genau einmal besucht? Zeigen Sie, dass \problem{HamiltonianPath} NP-vollständig ist. \emph{Hinweis: Reduzieren Sie \problem{HamiltonianCycle}.} \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$ und Zertifikat: eine Knotenfolge $(v_1, \dots, v_n)$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe, ob $(v_1, \dots, v_n)$ jeden Knoten aus $V$ genau einmal enthält; lehne sonst ab. \item Prüfe für jedes $i < n$, ob $\{v_i, v_{i+1}\} \in E$ gilt; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Hat $G$ einen Hamiltonpfad, dann ist seine Knotenfolge ein akzeptiertes Zertifikat. Hat $G$ keinen, dann scheitert jedes Zertifikat an einer Prüfung -- abgelehnt. \textbf{Laufzeit:} Knoten auf Vollständigkeit zählen $O(|V|)$, Kantenprüfungen $O(|V|)$ -- gesamt $O(|V|)$. Also gilt $\problem{HamiltonianPath} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{HamiltonianCycle} \redp \problem{HamiltonianPath}. \] \problem{HamiltonianCycle} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $G = (V,E)$ gegeben, o.B.d.A.\ $|V| \ge 3$. Wähle einen festen Knoten $v \in V$. Konstruiere $G' = (V', E')$ durch: \begin{itemize} \item $V' = V \cup \{v^*, s, t\}$ \item $E' = E \cup \{\{v^*, w\} \mid \{v,w\} \in E\} \cup \{\{s,v\}, \{t,v^*\}\}$ \end{itemize} Der Zwilling $v^*$ erbt die Nachbarn von $v$; die Pendants $s,t$ haben Grad 1. \textbf{Beweis HamiltonianCycle nach HamiltonianPath:} \begin{itemize} \item Sei $v, w_1, \dots, w_{n-1}, v$ ein Hamiltonkreis in $G$. \item Da $v^*$ dieselben Nachbarn wie $v$ hat, existiert die Kante $\{w_{n-1}, v^*\}$. \item Also ist $s, v, w_1, \dots, w_{n-1}, v^*, t$ ein Hamiltonpfad in $G'$. \end{itemize} \textbf{Beweis HamiltonianPath nach HamiltonianCycle:} \begin{itemize} \item Sei $P$ ein Hamiltonpfad in $G'$. \item $s$ und $t$ haben Grad 1, sind also die beiden Endpunkte von $P$. \item Da $s$ nur an $v$ und $t$ nur an $v^*$ hängt, hat $P$ die Form $s, v, x_1, \dots, x_{n-1}, v^*, t$. \item Dann sind $x_1, \dots, x_{n-1}$ alle Knoten aus $V \setminus \{v\}$. \item Da $\{x_{n-1}, v^*\} \in E'$ und $v^*$ dieselben Nachbarn wie $v$ hat, ist $x_{n-1}$ auch Nachbar von $v$. \item Ersetze $v^*$ durch $v$: Es entsteht der Kreis $v, x_1, \dots, x_{n-1}, v$, der jeden Knoten von $G$ genau einmal besucht. \item Also ist er ein Hamiltonkreis in $G$. \end{itemize} \textbf{Laufzeit:} Zwilling mit bis zu $|V|$ Nachbarn und zwei Pendants anlegen -- $O(|V|)$. Da \problem{HamiltonianCycle} NP-schwer ist, $\problem{HamiltonianCycle} \redp \problem{HamiltonianPath}$ gilt und $\problem{HamiltonianPath} \in \NP$, ist \problem{HamiltonianPath} NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für Hitchhiker's-HamiltonianCycle} \textbf{Problem \problem{Hitchhiker's-HamiltonianCycle}:} Gegeben ein ungerichteter Graph $G = (V,E)$ mit $\deg(v) \ge 42$ für alle $v \in V$. Entscheide: Gibt es einen Hamiltonkreis? Zeigen Sie, dass das Problem NP-vollständig ist. \emph{Hinweis: Reduzieren Sie \problem{HamiltonianCycle}.} \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$ und Zertifikat: eine Knotenfolge $(v_1, \dots, v_n)$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jeden Knoten $v \in V$, ob $\deg(v) \ge 42$ gilt; lehne sonst ab. \item Prüfe, ob $(v_1, \dots, v_n)$ jeden Knoten aus $V$ genau einmal enthält; lehne sonst ab. \item Prüfe für jedes $i < n$, ob $\{v_i, v_{i+1}\} \in E$, und ob $\{v_n, v_1\} \in E$ gilt; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Ist die Instanz gültig und hat $G$ einen Hamiltonkreis, dann ist dessen Knotenfolge ein akzeptiertes Zertifikat; sonst scheitert jedes Zertifikat an einer Prüfung -- abgelehnt. \textbf{Laufzeit:} Gradprüfung $O(|V| + |E|)$, Folge zählen $O(|V|)$, Kantenprüfungen $O(|V|)$ -- gesamt $O(|V| + |E|)$. Also gilt $\problem{Hitchhiker's-HamiltonianCycle} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{HamiltonianCycle} \redp \problem{Hitchhiker's-HamiltonianCycle}. \] \problem{HamiltonianCycle} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $G = (V,E)$ gegeben. Ersetze jeden Knoten $v$ durch eine Clique $K_{43}$ auf $\{v_1, \dots, v_{43}\}$ (Portale sind $v_1$ und $v_{43}$). Konstruiere $G' = (V', E')$ durch: \begin{itemize} \item $V' = \{v_1, \dots, v_{43} \mid v \in V\}$ \item $E' = \{\{v_i, v_j\} \mid v \in V,\ i \ne j\} \cup \{\{u_i, v_j\} \mid \{u,v\} \in E,\ i,j \in \{1,43\}\}$ \end{itemize} Innere Clique-Knoten haben Grad $42$, die Portale Grad $\ge 42$ -- die Instanz ist gültig. \begin{center} \begin{tikzpicture}[scale=0.9] \node[knoten,font=\small] (u1) at (0,0.85) {$u_1$}; \node[knoten,font=\small] (u43) at (0,-0.85) {$u_{43}$}; \node[knoten,font=\small] (v1) at (2.9,0.85) {$v_1$}; \node[knoten,font=\small] (v43) at (2.9,-0.85) {$v_{43}$}; \draw (u1)--(v1) (u1)--(v43) (u43)--(v1) (u43)--(v43); \draw[dashed] (0,0) ellipse [x radius=0.55, y radius=1.45]; \draw[dashed] (2.9,0) ellipse [x radius=0.55, y radius=1.45]; \node[font=\footnotesize] at (0,-2.0) {Clique $K_{43}$ von $u$}; \node[font=\footnotesize] at (2.9,-2.0) {Clique $K_{43}$ von $v$}; \node[font=\footnotesize,align=center] at (1.45,2.05) {vier Portalkanten\\ pro Originalkante $\{u,v\}$}; \end{tikzpicture} \end{center} \textbf{Beweis HamiltonianCycle nach Hitchhiker's-HamiltonianCycle:} \begin{itemize} \item Sei $v^{(1)}, \dots, v^{(n)}, v^{(1)}$ ein Hamiltonkreis in $G$. \item Durchlaufe die Clique jedes $v^{(j)}$ auf dem Pfad $v^{(j)}_1 \to \dots \to v^{(j)}_{43}$; dieser Pfad existiert in jeder Clique. \item Wechsle über die Portalkante $\{v^{(j)}_{43}, v^{(j+1)}_1\}$ zur nächsten Clique. \item Diese Kante existiert, denn $\{v^{(j)}, v^{(j+1)}\} \in E$. \item Also wird jeder Knoten von $G'$ genau einmal besucht -- ein Hamiltonkreis in $G'$. \end{itemize} \textbf{Beweis Hitchhiker's-HamiltonianCycle nach HamiltonianCycle:} \begin{itemize} \item Sei $C'$ ein Hamiltonkreis in $G'$. \item Innere Clique-Knoten haben nur Nachbarn in der eigenen Clique; nach außen führen nur die Portalkanten. \item Somit durchläuft $C'$ jede Clique als ein Segment von Portal zu Portal. \item Ziehe jede Clique auf ihren Originalknoten zusammen. \item Jede benutzte Portalkante stammt von einer Originalkante $\{u,v\} \in E$. \item Also entsteht ein Kreis in $G$, der jeden Knoten genau einmal besucht -- ein Hamiltonkreis in $G$. \end{itemize} \textbf{Laufzeit:} Pro Knoten eine $K_{43}$ mit $43^2$ Kanten, pro Kante vier Portalkanten -- $O(43^2 \cdot |V| + |E|)$. Da das Problem in $\NP$ liegt und NP-schwer ist, folgt: \problem{Hitchhiker's-HamiltonianCycle} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für TSP-Entscheidung} \textbf{Problem \problem{TSP-Entscheidung}:} Gegeben $n$ Städte mit Distanzen $d(u,v) > 0$ und eine Schranke $L$. Gibt es eine Rundtour der Länge $\le L$ durch alle Städte? Beweisen Sie, dass das Problem NP-vollständig ist. \emph{Hinweis:} Reduzieren Sie \problem{HamiltonianCycle}. \lsg \textbf{$\in$ NP:} Eingabe: Distanzen, Schranke $L$ und Zertifikat: eine Rundtour $\pi$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe, ob $\pi$ jede Stadt genau einmal besucht; lehne sonst ab. \item Summiere die Distanzen entlang $\pi$; lehne ab, falls $> L$. \item Sonst akzeptiere. \end{itemize} Existiert eine Tour der Länge $\le L$, wird sie akzeptiert; sonst scheitert jedes Zertifikat. Besuchsprüfung und Summieren -- $O(n^2)$. Also liegt \problem{TSP-Entscheidung} in $\NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{HamiltonianCycle} \redp \problem{TSP-Entscheidung}. \] \problem{HamiltonianCycle} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $G = (V,E)$ eine \problem{HamiltonianCycle}-Instanz mit $n = |V|$. Wir konstruieren daraus: \begin{itemize} \item Städte $= V$ \item $d(u,v) = 1$ falls $\{u,v\} \in E$, sonst $d(u,v) = n+1$ \item $L = n$ \end{itemize} \textbf{Beweis HamiltonianCycle nach TSP:} \begin{itemize} \item Sei $C$ ein Hamiltonkreis in $G$. \item $C$ ist eine Rundtour aus $n$ Kanten mit Distanz je $1$. \item Also hat die Tour Länge $n \le L$. \end{itemize} \textbf{Beweis TSP nach HamiltonianCycle:} \begin{itemize} \item Sei $\pi$ eine Rundtour der Länge $\le n$. \item $\pi$ hat $n$ Schritte, jeder kostet mindestens $1$. \item Enthielte $\pi$ eine Nicht-Kante, wäre die Länge $\ge (n-1) + (n+1) = 2n > n$. \item Also nutzt $\pi$ nur Kanten aus $E$ -- $\pi$ ist ein Hamiltonkreis. \end{itemize} \textbf{Laufzeit:} Alle Paare belegen -- $O(n^2)$. Da \problem{TSP-Entscheidung} $\in \NP$ und NP-schwer ist, folgt: \problem{TSP-Entscheidung} ist NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für $k$-CLIQUE-DEG-3} \textbf{Problem $k$-\problem{CLIQUE-DEG-3}:} Gegeben $G = (V,E)$ mit $\deg(v) \ge 3$ für alle $v \in V$ und $k \in \mathbb{N}_{>0}$. Entscheide: Gibt es eine Clique $C$ mit $|C| \ge k$? Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Reduzieren Sie $k$-\problem{Clique}.} \lsg \textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat $C \subseteq V$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jeden Knoten $v \in V$, ob $\deg(v) \ge 3$ gilt; lehne sonst ab. \item Falls $|C| < k$, lehne ab. \item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$ gilt; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Ist die Instanz gültig und hat $G$ eine Clique mit $|C| \ge k$, dann ist diese ein akzeptiertes Zertifikat; sonst verletzt jedes Zertifikat eine Prüfung -- abgelehnt. \textbf{Laufzeit:} Gradprüfung $O(|V| + |E|)$, Größe zählen $O(|V|)$, alle Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt $k\text{-}\problem{CLIQUE-DEG-3} \in \NP$. \textbf{Fall $k \le 4$:} Teste jede Knotenmenge $C \subseteq V$ mit $|C| = k$ und prüfe alle Paare per Adjazenzmatrix. Es gibt $O(|V|^k) \subseteq O(|V|^4)$ Mengen mit je $O(1)$ Prüfaufwand -- gesamt $O(|V|^4)$. Für $k \le 4$ ist das Problem also direkt lösbar; die Konstruktion nimmt daher o.B.d.A.\ $k \ge 5$ an. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ k\text{-}\problem{Clique} \redp k\text{-}\problem{CLIQUE-DEG-3}. \] $k$-\problem{Clique} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(G = (V,E), k)$ eine $k$-\problem{Clique}-Instanz, o.B.d.A.\ $k \ge 5$. Hänge an jeden Knoten $v$ ein privates $K_4$. Konstruiere $(G' = (V', E'), k')$ durch: \begin{itemize} \item $V' = V \cup \{a_v, b_v, c_v \mid v \in V\}$ \item $E' = E \cup \{\{x,y\} \mid v \in V,\ x,y \in \{v, a_v, b_v, c_v\},\ x \ne y\}$ \item $k' = k$ \end{itemize} Jedes $v \in V$ hat die drei Nachbarn $a_v, b_v, c_v$, Gadget-Knoten haben Grad genau 3 -- die Instanz ist gültig. \textbf{Beweis $k$-Clique nach $k$-CLIQUE-DEG-3} (Fall $k \ge 5$): \begin{itemize} \item Sei $C$ eine $k$-Clique in $G$. \item Es wurde keine Kante entfernt. \item Also ist $C$ auch eine $k$-Clique in $G'$. \end{itemize} \textbf{Beweis $k$-CLIQUE-DEG-3 nach $k$-Clique} (Fall $k \ge 5$): \begin{itemize} \item Sei $C'$ eine $k$-Clique in $G'$. \item Jeder Knoten in $C'$ hat mindestens $k - 1 \ge 4$ Nachbarn innerhalb $C'$. \item Gadget-Knoten haben Grad $3 < 4$, können also keine vier Clique-Nachbarn haben. \item Somit liegt kein Gadget-Knoten in $C'$, also $C' \subseteq V$. \item Zwischen Knoten aus $V$ kam keine Kante hinzu. \item Also ist $C'$ eine $k$-Clique in $G$. \end{itemize} Im Fall $k \le 4$ wird $(G,k)$ direkt gelöst und eine triviale Instanz mit gleicher Antwort ausgegeben. \textbf{Laufzeit:} Pro Knoten ein $K_4$-Gadget konstanter Größe -- $O(|V|)$; im Fall $k \le 4$ alle Mengen testen -- $O(|V|^4)$. Da $k\text{-}\problem{CLIQUE-DEG-3} \in \NP$ und NP-schwer ist, ist $k$-\problem{CLIQUE-DEG-3} NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für Partition} \textbf{Problem \problem{Partition}:} Gegeben Zahlen $c_1, \dots, c_n$. Entscheide: Gibt es $S$ mit $\sum_{j\in S} c_j = \frac12 \sum_{j=1}^{n} c_j$? Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Reduzieren Sie \problem{SubsetSum}.} \lsg \textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$ und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Berechne $\Sigma = \sum_{j=1}^{n} c_j$. \item Prüfe $\sum_{j\in S} c_j = \Sigma / 2$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Gibt es eine Partition, dann ist eine ihrer Seiten ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt. \textbf{Laufzeit:} Zwei Summen bilden und vergleichen -- $O(n)$. Also gilt $\problem{Partition} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SubsetSum} \redp \problem{Partition}. \] \problem{SubsetSum} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine \problem{SubsetSum}-Instanz. Setze $N := \sum_{j=1}^{n} c_j + 1$ und hänge zwei Ausgleichszahlen an: \[ c_{n+1} := N - K, \qquad c_{n+2} := K + 1. \] Die neue Gesamtsumme ist $(N-1) + (N-K) + (K+1) = 2N$, die Hälfte also $N$. \textbf{Schlüsselbeobachtung:} $c_{n+1} + c_{n+2} = N + 1 > N$ -- in jeder Partition liegen die beiden Ausgleichszahlen auf verschiedenen Seiten. \textbf{Beweis SubsetSum nach Partition:} \begin{itemize} \item Sei $S \subseteq [n]$ mit $\sum_{j\in S} c_j = K$. \item Setze $S' := S \cup \{n{+}1\}$. \item Dann gilt $\sum_{j\in S'} c_j = K + (N - K) = N$. \item Also ist $S'$ eine Seite halber Gesamtsumme -- eine Partition. \end{itemize} \textbf{Beweis Partition nach SubsetSum:} \begin{itemize} \item Sei $S'$ eine Seite mit $\sum_{j\in S'} c_j = N$. \item Nach der Schlüsselbeobachtung liegen $n{+}1$ und $n{+}2$ auf verschiedenen Seiten. \item O.B.d.A.\ $n{+}1 \in S'$ und $n{+}2 \notin S'$. \item Setze $S := S' \setminus \{n{+}1\} \subseteq [n]$. \item Dann gilt $\sum_{j\in S} c_j = N - (N - K) = K$ -- eine SubsetSum-Lösung. \end{itemize} \textbf{Laufzeit:} Gesamtsumme berechnen und zwei Zahlen anhängen -- $O(n)$. Da \problem{SubsetSum} NP-vollständig ist, $\problem{SubsetSum} \redp \problem{Partition}$ gilt und $\problem{Partition} \in \NP$, ist \problem{Partition} NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für SubsetSumCardinality} \textbf{Problem \problem{SubsetSumCardinality}:} Gegeben $c_1, \dots, c_n$ ($n$ gerade) und $K$. Entscheide: Gibt es $S$ mit $|S| = n/2$ und $\sum_{i\in S} c_i = K$? Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Reduzieren Sie \problem{SubsetSum}.} \lsg \textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$ ($n$ gerade), Zielwert $K$ und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe $|S| = n/2$; lehne sonst ab. \item Prüfe $\sum_{i\in S} c_i = K$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Gibt es eine Lösung passender Größe und Summe, dann ist sie ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt. \textbf{Laufzeit:} $|S|$ zählen und Summe bilden -- $O(n)$. Also gilt $\problem{SubsetSumCardinality} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SubsetSum} \redp \problem{SubsetSumCardinality}. \] \problem{SubsetSum} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine \problem{SubsetSum}-Instanz. Shifte alle Größen um $1$ und füge $n$ Padding-Items der Größe $1$ hinzu: \[ c_i' := c_i + 1 \ \ (i \le n), \qquad c_i' := 1 \ \ (n < i \le 2n), \qquad K' := K + n. \] Die Ausgabeinstanz hat $2n$ (gerade) Items und verlangt $|S'| = n$. \textbf{Beweis SubsetSum nach SubsetSumCardinality:} \begin{itemize} \item Sei $S \subseteq [n]$ mit $\sum_{i\in S} c_i = K$. \item Dann gilt $\sum_{i\in S} c_i' = \sum_{i\in S}(c_i + 1) = K + |S|$. \item Setze $S' := S \cup \{n{+}1, \dots, 2n - |S|\}$, also $n - |S|$ Padding-Items dazu. \item Dann gilt $|S'| = |S| + (n - |S|) = n$. \item Und $\sum_{i\in S'} c_i' = (K + |S|) + (n - |S|) = K + n = K'$. \item Also ist $S'$ eine Lösung der neuen Instanz. \end{itemize} \textbf{Beweis SubsetSumCardinality nach SubsetSum:} \begin{itemize} \item Sei $S'$ mit $|S'| = n$ und $\sum_{i\in S'} c_i' = K + n$. \item Setze $S := S' \cap [n]$; dann enthält $S'$ genau $n - |S|$ Padding-Items. \item Es folgt $\sum_{i\in S}(c_i + 1) = (K + n) - (n - |S|) = K + |S|$. \item Also $\sum_{i\in S} c_i = K$ -- eine SubsetSum-Lösung. \end{itemize} \textbf{Laufzeit:} $n$ Zahlen shiften und $n$ Padding-Items anhängen -- $O(n)$. Da \problem{SubsetSum} NP-vollständig ist, $\problem{SubsetSum} \redp \problem{SubsetSumCardinality}$ gilt und $\problem{SubsetSumCardinality} \in \NP$, ist \problem{SubsetSumCardinality} NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für $(a_1{=}1)$-SubsetSum} \textbf{Problem $(a_1{=}1)$-\problem{SubsetSum}:} Gegeben $n$ Items mit Größen $a_i \in \mathbb{N}_{>0}$, wobei $a_1 = 1$, und Zielwert $T$. Entscheide: Gibt es $I \subseteq [n]$ mit $\sum_{i\in I} a_i = T$? Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Reduzieren Sie \problem{SubsetSum}.} \lsg \textbf{$\in$ NP:} Eingabe: Größen $a_1, \dots, a_n$, Zielwert $T$ und Zertifikat $I \subseteq [n]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe $a_1 = 1$; lehne sonst ab. \item Prüfe $\sum_{i\in I} a_i = T$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Ist die Instanz gültig und hat sie eine Lösung, dann ist diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt. \textbf{Laufzeit:} $a_1$ prüfen und Summe bilden -- $O(n)$. Also gilt $(a_1{=}1)\text{-}\problem{SubsetSum} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SubsetSum} \redp (a_1{=}1)\text{-}\problem{SubsetSum}. \] \problem{SubsetSum} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine \problem{SubsetSum}-Instanz. Verdopple alle Größen und stelle ein Ballast-Item voran: \[ a_1 := 1, \qquad a_{i+1} := 2 c_i \ \ (i \in [n]), \qquad T := 2K. \] Wegen $a_1 = 1$ ist die Instanz gültig. \textbf{Beweis SubsetSum nach $(a_1{=}1)$-SubsetSum:} \begin{itemize} \item Sei $S$ mit $\sum_{i\in S} c_i = K$. \item Setze $I := \{i + 1 \mid i \in S\}$. \item Dann gilt $\sum_{j\in I} a_j = \sum_{i\in S} 2 c_i = 2K = T$. \item Also ist $I$ eine Lösung der neuen Instanz. \end{itemize} \textbf{Beweis $(a_1{=}1)$-SubsetSum nach SubsetSum:} \begin{itemize} \item Sei $I$ mit $\sum_{i\in I} a_i = T = 2K$. \item Alle Items außer $a_1$ sind gerade, und $T = 2K$ ist gerade. \item Angenommen $1 \in I$: Dann wäre die Summe ungerade, da $a_1 = 1$ das einzige ungerade Item ist -- Widerspruch. \item Also $1 \notin I$; setze $S := \{i - 1 \mid i \in I\}$. \item Dann gilt $\sum_{i\in S} 2 c_i = 2K$, also $\sum_{i\in S} c_i = K$ -- eine SubsetSum-Lösung. \end{itemize} \textbf{Laufzeit:} $n$ Zahlen verdoppeln und das Ballast-Item voranstellen -- $O(n)$. Da \problem{SubsetSum} NP-vollständig ist, die Reduktion gilt und $(a_1{=}1)\text{-}\problem{SubsetSum} \in \NP$, ist $(a_1{=}1)$-\problem{SubsetSum} NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für SubsetSum mit Teilbarkeit} Sei $L$ die Menge der \problem{SubsetSum}-Instanzen, bei denen jede Itemgröße durch $3$ oder durch $7$ teilbar ist. Entscheide: Gibt es $S$ mit $\sum_{i\in S} c_i = K$? Zeigen Sie, dass $L$ NP-vollständig ist. \emph{Hinweis: Reduzieren Sie \problem{SubsetSum}.} \lsg \textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$, Zielwert $K$ und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jede Größe $c_i$, ob $3 \mid c_i$ oder $7 \mid c_i$ gilt; lehne sonst ab. \item Prüfe $\sum_{i\in S} c_i = K$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Ist die Instanz eine gültige Variante mit Lösung, dann ist diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt. \textbf{Laufzeit:} Teilbarkeitstests und Summe bilden -- $O(n)$. Also gilt $L \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SubsetSum} \redp L. \] \problem{SubsetSum} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine \problem{SubsetSum}-Instanz. Skaliere mit $3$: \[ c_i' := 3 c_i \ \ (i \in [n]), \qquad K' := 3K. \] Jede Größe $c_i'$ ist durch $3$ teilbar -- die Instanz liegt in $L$. \textbf{Beweis SubsetSum nach Variante:} \begin{itemize} \item Sei $S$ mit $\sum_{i\in S} c_i = K$. \item Dann gilt $\sum_{i\in S} c_i' = \sum_{i\in S} 3 c_i = 3 \sum_{i\in S} c_i = 3K = K'$. \item Also ist $S$ eine Lösung der neuen Instanz. \end{itemize} \textbf{Beweis Variante nach SubsetSum:} \begin{itemize} \item Sei $S$ mit $\sum_{i\in S} c_i' = K'$. \item Wegen $c_i' = 3 c_i$ heißt das $3 \sum_{i\in S} c_i = 3K$. \item Division durch $3$ liefert $\sum_{i\in S} c_i = K$. \item Also ist $S$ eine SubsetSum-Lösung. \end{itemize} \textbf{Laufzeit:} Jede der $n$ Zahlen und $K$ mit $3$ multiplizieren -- $O(n)$. Da \problem{SubsetSum} NP-vollständig ist, $\problem{SubsetSum} \redp L$ gilt und $L \in \NP$, ist $L$ NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für SubsetSum ohne Zweierpotenzen} Sei $L$ die Menge der \problem{SubsetSum}-Instanzen, bei denen keine Itemgröße eine Zweierpotenz ist. Entscheide: Gibt es $S$ mit $\sum_{i\in S} c_i = K$? Zeigen Sie, dass $L$ NP-vollständig ist. \emph{Hinweis: Reduzieren Sie \problem{SubsetSum}.} \lsg \textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$, Zielwert $K$ und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jede Größe $c_i$, dass sie keine Zweierpotenz ist ($c_i$ ist Zweierpotenz genau dann, wenn $c_i \wedge (c_i - 1) = 0$); lehne sonst ab. \item Prüfe $\sum_{i\in S} c_i = K$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Ist die Instanz eine gültige Variante mit Lösung, dann ist diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt. \textbf{Laufzeit:} Bit-Test je Größe und Summe bilden -- $O(n)$. Also gilt $L \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SubsetSum} \redp L. \] \problem{SubsetSum} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine \problem{SubsetSum}-Instanz. Skaliere mit $3$: \[ c_i' := 3 c_i \ \ (i \in [n]), \qquad K' := 3K. \] Jede Größe $c_i' \ge 3$ hat den Primfaktor $3$; Zweierpotenzen haben nur den Primfaktor $2$. Also ist kein $c_i'$ eine Zweierpotenz -- die Instanz liegt in $L$. \textbf{Beweis SubsetSum nach Variante:} \begin{itemize} \item Sei $S$ mit $\sum_{i\in S} c_i = K$. \item Dann gilt $\sum_{i\in S} c_i' = 3 \sum_{i\in S} c_i = 3K = K'$. \item Also ist $S$ eine Lösung der neuen Instanz. \end{itemize} \textbf{Beweis Variante nach SubsetSum:} \begin{itemize} \item Sei $S$ mit $\sum_{i\in S} c_i' = K'$. \item Das heißt $3 \sum_{i\in S} c_i = 3K$. \item Division durch $3$ liefert $\sum_{i\in S} c_i = K$. \item Also ist $S$ eine SubsetSum-Lösung. \end{itemize} \textbf{Laufzeit:} Jede der $n$ Zahlen und $K$ mit $3$ multiplizieren -- $O(n)$. Da \problem{SubsetSum} NP-vollständig ist, $\problem{SubsetSum} \redp L$ gilt und $L \in \NP$, ist $L$ NP-vollständig. \hfill$\square$ \aufg{NP-Vollständigkeit zeigen für AtMostTwoPerSize-SubsetSum} \textbf{Problem \problem{AtMostTwoPerSize-SubsetSum}:} Gegeben ein Zielwert $T > 0$ und $n$ Items mit Größen $a_i \in \mathbb{N}_{>0}$, wobei jede Größe höchstens zweimal auftritt. Entscheide: Gibt es $S$ mit $\sum_{i\in S} a_i = T$? Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Bei \problem{3-ExactCover} sind ein Universum $U$ mit $|U| = 3m$ und Dreiermengen $S_1, \dots, S_n \subseteq U$ gegeben; gesucht ist eine Auswahl, die jedes Element genau einmal überdeckt. Reduzieren Sie \problem{3-ExactCover}.} \lsg \textbf{$\in$ NP:} Eingabe: Größen $a_1, \dots, a_n$, Zielwert $T$ und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jede Größe, ob sie unter $a_1, \dots, a_n$ höchstens zweimal vorkommt; lehne sonst ab. \item Prüfe $\sum_{i\in S} a_i = T$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Ist die Instanz eine gültige Variante mit Lösung, dann ist diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt. \textbf{Laufzeit:} Häufigkeiten per Paarvergleich $O(n^2)$ und Summe bilden $O(n)$ -- gesamt $O(n^2)$. Also gilt $\problem{AtMostTwoPerSize-SubsetSum} \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{3-ExactCover} \redp \problem{AtMostTwoPerSize-SubsetSum}. \] \problem{3-ExactCover} ist bereits als NP-schwer bekannt. \textbf{Konstruktion:} Sei $(U, S_1, \dots, S_n)$ eine \problem{3-ExactCover}-Instanz mit $U = \{u_1, \dots, u_{3m}\}$, o.B.d.A.\ die $S_j$ paarweise verschieden (Duplikate vorab löschen). Kodiere jede Menge als Ziffernzahl in Basis $n+1$: \begin{itemize} \item $c_j := \sum_{u_i \in S_j} (n+1)^{i-1}$ für $j = 1, \dots, n$ -- Ziffer $1$ an den drei Stellen der Elemente von $S_j$ \item $T := \sum_{j=0}^{3m-1} (n+1)^j$ -- an jeder der $3m$ Stellen eine $1$ \end{itemize} Verschiedene Mengen setzen verschiedene Potenzen, also sind $c_1, \dots, c_n$ paarweise verschieden -- jede Größe tritt nur einmal auf, die Instanz ist gültig. \textbf{Beweis 3-ExactCover nach AtMostTwoPerSize-SubsetSum:} \begin{itemize} \item Sei $\mathcal{S}$ eine exakte Überdeckung. \item Jedes Element $u_i$ wird von genau einer Menge in $\mathcal{S}$ überdeckt. \item Also kommt in $\sum_{S_j \in \mathcal{S}} c_j$ jede Potenz $(n+1)^{i-1}$ genau einmal vor. \item Damit gilt $\sum_{S_j \in \mathcal{S}} c_j = \sum_{j=0}^{3m-1} (n+1)^j = T$. \item Also ist $\mathcal{S}$ eine Lösung der SubsetSum-Instanz. \end{itemize} \textbf{Beweis AtMostTwoPerSize-SubsetSum nach 3-ExactCover:} \begin{itemize} \item Sei $S$ eine Auswahl mit $\sum_{j\in S} c_j = T$. \item An jeder Ziffernstelle addieren sich höchstens $n$ Einsen, da es nur $n$ Mengen gibt. \item Da die Basis $n+1$ ist, entsteht beim Addieren kein Übertrag. \item In $T$ hat jede der $3m$ Stellen den Wert $1$. \item Also trägt zu jeder Stelle genau eine gewählte Menge bei. \item Damit überdecken die gewählten Mengen jedes Element genau einmal -- eine exakte Überdeckung. \end{itemize} \textbf{Laufzeit:} Duplikate per Paarvergleich der $n$ Mengen entfernen -- $O(n^2)$; pro Menge drei Potenzen von $n+1$ und $T$ aus $3m$ Potenzen aufaddieren -- $O(n + m)$ Additionen. Da das Problem in $\NP$ liegt und NP-schwer ist, folgt: \problem{AtMostTwoPerSize-SubsetSum} ist NP-vollständig. \hfill$\square$ \aufg{NP-Schwere zeigen für HALT$_{\text{TM}}$} $\mathrm{HALT}_{\mathrm{TM}} := \{\langle M, w\rangle \mid M \text{ ist eine DTM und hält auf } w\}$. Zeigen Sie, dass $\mathrm{HALT}_{\mathrm{TM}}$ NP-schwer ist, und begründen Sie, warum $\mathrm{HALT}_{\mathrm{TM}} \notin \NP$. \emph{Hinweis: Reduzieren Sie \problem{SAT}.} \lsg \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SAT} \redp \mathrm{HALT}_{\mathrm{TM}}. \] \problem{SAT} ist bereits als NP-schwer bekannt. \textbf{Konstruktion:} Sei $\varphi$ eine \problem{SAT}-Instanz über den Variablen $x_1, \dots, x_n$. Gib die Instanz $\langle M, w \rangle$ aus: \begin{itemize} \item $w := \langle \varphi \rangle$ -- die Kodierung von $\varphi$. \item $M$ ist eine feste DTM, die auf Eingabe $\langle \varphi \rangle$ so arbeitet: probiere nacheinander alle $2^n$ Belegungen der Variablen; halte, sobald eine Belegung $\varphi$ erfüllt; gehe in eine Endlosschleife, falls keine der $2^n$ Belegungen erfüllt. \end{itemize} \textbf{Beweis SAT nach HALT:} \begin{itemize} \item Sei $\varphi \in \problem{SAT}$. \item Dann existiert eine erfüllende Belegung. \item $M$ probiert alle Belegungen, findet diese und hält auf $w$. \item Also $\langle M, w \rangle \in \mathrm{HALT}_{\mathrm{TM}}$. \end{itemize} \textbf{Beweis HALT nach SAT:} \begin{itemize} \item Sei $\langle M, w \rangle \in \mathrm{HALT}_{\mathrm{TM}}$, also hält $M$ auf $w$. \item $M$ hält nur, wenn es eine erfüllende Belegung findet. \item Denn ohne erfüllende Belegung geht $M$ in die Endlosschleife. \item Also existiert eine erfüllende Belegung für $\varphi$. \item Damit $\varphi \in \problem{SAT}$. \end{itemize} \textbf{Laufzeit:} Nur $\varphi$ kodieren und die feste Maschine $M$ ausgeben -- $O(|\varphi|)$. Ob $M$ auf $w$ hält, spielt für die Reduktion keine Rolle. Da \problem{SAT} NP-schwer ist und $\problem{SAT} \redp \mathrm{HALT}_{\mathrm{TM}}$ gilt, ist $\mathrm{HALT}_{\mathrm{TM}}$ NP-schwer. \textbf{Warum $\mathrm{HALT}_{\mathrm{TM}} \notin \NP$:} $\mathrm{HALT}_{\mathrm{TM}}$ ist das Halteproblem und damit unentscheidbar. Jede Sprache in $\NP$ ist jedoch entscheidbar: Ein Verifizierer liefert durch Absuchen aller polynomiell langen Zertifikate ein Entscheidungsverfahren. Eine unentscheidbare Sprache kann also nicht in $\NP$ liegen. Somit ist $\mathrm{HALT}_{\mathrm{TM}}$ NP-schwer, aber nicht NP-vollständig. \hfill$\square$ \clearpage \section{Approximative Algorithmen} \aufg{Güte zeigen für ListScheduling} $P\,\|\,C_{\max}$: $n$ Jobs mit Zeiten $p_1,\dots,p_n$ auf $m$ Maschinen, minimiere den Makespan. \emph{Hinweis:} ListScheduling legt jeden Job der Reihe nach auf die aktuell am wenigsten belastete Maschine. Zeigen Sie die Güte $2-\frac1m$. \lsg Zu zeigen: \[ \mathrm{LS}(I) \;\le\; \Bigl(2-\tfrac1m\Bigr)\,\mathrm{OPT}(I) . \] O.\,B.\,d.\,A.\ trage Maschine $M_1$ am Ende die höchste Last $L=\mathrm{LS}(I)$, und sei $J_k$ der \emph{letzte} Job, der auf $M_1$ gelegt wurde. \textbf{Kritischer Moment.} Als $J_k$ zugeteilt wurde, war $M_1$ die leerste Maschine mit Last $L-p_k$. Also trugen zu diesem Zeitpunkt alle $m$ Maschinen mindestens Last $L-p_k$, woraus für die Gesamtarbeit folgt \[ \sum_{i=1}^{n} p_i \;\ge\; m\,(L-p_k) + p_k . \] \textbf{Untere Schranken für das Optimum.} Die Gesamtarbeit verteilt sich auf $m$ Maschinen, und jeder Job läuft irgendwo, also \[ \mathrm{OPT}(I) \;\ge\; \frac1m\sum_{i=1}^n p_i \qquad\text{und}\qquad \mathrm{OPT}(I) \;\ge\; p_k . \] \textbf{Kombination.} Erst die Durchschnittsschranke mit der Kernbeobachtung verbinden: \[ \mathrm{OPT}(I) \;\ge\; \frac1m\sum_{i=1}^n p_i \;\ge\; \frac{m(L-p_k)+p_k}{m} \;=\; L - p_k + \frac{p_k}{m} \;=\; L-\Bigl(1-\tfrac1m\Bigr)p_k . \] Nach $L$ aufgelöst: \[ \mathrm{LS}(I) \;=\; L \;\le\; \mathrm{OPT}(I) + \Bigl(1-\tfrac1m\Bigr)p_k . \] Nun $p_k \le \mathrm{OPT}(I)$ einsetzen: \[ \mathrm{LS}(I) \;\le\; \mathrm{OPT}(I) + \Bigl(1-\tfrac1m\Bigr)\mathrm{OPT}(I) \;=\; \Bigl(2-\tfrac1m\Bigr)\mathrm{OPT}(I) . \] Somit hat ListScheduling die Güte $2-\frac1m$. \aufg{Güte zeigen für LPT} $P\,\|\,C_{\max}$ wie zuvor. \emph{Hinweis:} LPT sortiert die Jobs zuerst \emph{absteigend} nach Laufzeit und wendet darauf ListScheduling an. Zeigen Sie die Güte $\frac43-\frac1{3m}$. \lsg Zu zeigen: \[ \mathrm{LPT}(I) \;\le\; \Bigl(\tfrac43-\tfrac1{3m}\Bigr)\,\mathrm{OPT}(I) . \] Nummeriere absteigend, $p_1\ge\dots\ge p_n$. Sei $J_n$ der Job, der den Makespan setzt (der kleinste Job auf der vollsten Maschine). \textbf{Kritischer Moment.} Als $J_n$ platziert wurde, hatte seine Maschine die kleinste Last $s$. Wie bei ListScheduling folgt $s \le \mathrm{OPT}(I) - p_n/m$, also \[ \mathrm{LPT}(I) \;=\; s+p_n \;\le\; \mathrm{OPT}(I) + \Bigl(1-\tfrac1m\Bigr)p_n . \] \textbf{Fallunterscheidung nach $p_n$.} \begin{itemize} \item Ist $p_n \le \mathrm{OPT}(I)/3$, so liefert Einsetzen direkt $\mathrm{LPT}(I) \le (\tfrac43-\tfrac1{3m})\,\mathrm{OPT}(I)$. \item Ist $p_n > \mathrm{OPT}(I)/3$, dann sind \emph{alle} Jobs $> \mathrm{OPT}(I)/3$. Im Optimum trägt jede Maschine höchstens zwei Jobs. Für diesen Fall ist bekannt, dass LPT sogar optimal ist ($\mathrm{LPT}(I) = \mathrm{OPT}(I)$). \end{itemize} In beiden Fällen gilt die Schranke, also hat LPT die Güte $\frac43-\frac1{3m}$. \aufg{Güte zeigen für RoundRobin} $P\,\|\,C_{\max}$ wie zuvor. \emph{Hinweis:} RoundRobin sortiert die Jobs absteigend und verteilt sie reihum, d.\,h.\ $J_j$ kommt auf Maschine $((j-1)\bmod m)+1$. Zeigen Sie die Güte $2$ (die Rate wird im Worst Case bis $2-\frac1m$ ausgereizt). \lsg Zu zeigen: \[ \mathrm{RR}(I) \;\le\; 2\,\mathrm{OPT}(I) . \] Angenommen, es gälte $\mathrm{RR}(I)>2\,\mathrm{OPT}(I)$. Sei $M_i$ die Maschine mit maximaler Last; sie trägt die Jobs $J_i,J_{i+m},J_{i+2m},\dots$ \textbf{Blockschranke.} Wegen der absteigenden Sortierung ist $p_{i+lm}\le p_j$ für jedes $j\le lm$; insbesondere ist $p_{i+lm}$ höchstens so groß wie der Durchschnitt des vorangehenden $m$-er-Blocks: \[ p_{i+lm} \;\le\; \frac1m\sum_{j=(l-1)m+1}^{lm} p_j \qquad (l\ge1). \] \textbf{Aufsummieren.} Summation über $l\ge1$ ergibt \[ \mathrm{RR}(I)-p_i \;=\; \sum_{l\ge1}p_{i+lm} \;\le\; \frac1m\sum_{j} p_j \;\le\; \mathrm{OPT}(I). \] \textbf{Kombination.} Mit $p_i\le p_1\le\mathrm{OPT}(I)$ folgt $\mathrm{RR}(I)\le 2\,\mathrm{OPT}(I)$ -- im Widerspruch zur Annahme. Somit hat RoundRobin die Güte $2$; die Familie aus einem Job der Größe $m$ und $m(m-1)$ Einser-Jobs treibt die Rate gegen $2-\frac1m$. \aufg{Güte zeigen für Parallel-Task-ListScheduling} Beim Parallel-Task-Scheduling belegt Job $j$ während seiner Laufzeit $p_j$ \emph{gleichzeitig} $q_j\in[m]$ Maschinen. \emph{Hinweis:} ListScheduling platziert jeden Job zum frühestmöglichen Zeitpunkt auf den $q_j$ am wenigsten belasteten Maschinen. Zeigen Sie für alle Instanzen mit $\frac m3m$ Maschinen). Also laufen genau zwei, und \[ 2s \;=\; \int_0^s \#\{\text{laufende Jobs}\}\;dt \;\le\; \sum_i p_i - p_j . \] \textbf{Schranke für das Optimum.} Auch im Optimum laufen nie drei Jobs gleichzeitig (sie bräuchten $>3\cdot\frac m3=m$ Maschinen), also $\sum_i p_i\le 2\,\mathrm{OPT}(I)$. Einsetzen: \[ s \;\le\; \tfrac12\Bigl(\sum_i p_i-p_j\Bigr) \;\le\; \mathrm{OPT}(I)-\tfrac12 p_j . \] \textbf{Kombination.} Mit $\mathrm{LS}(I)=s+p_j$ folgt \[ \mathrm{LS}(I) \;\le\; \mathrm{OPT}(I)+\tfrac12 p_j \;\le\; \mathrm{OPT}(I)+\tfrac12 p_{\max}. \] Somit gilt die behauptete Schranke. \aufg{Güte zeigen für ModifiedGreedy} \problem{Knapsack}: Gegenstände mit Gewichten $w_i$, Profiten $p_i$, Kapazität $B$; maximiere den Profit. \emph{Hinweis:} Greedy sortiert absteigend nach Profitdichte $p_i/w_i$ und packt in dieser Reihenfolge jeden Gegenstand ein, der noch passt; ModifiedGreedy (MGA) gibt das Bessere aus Greedy-Lösung und profitreichstem Einzel-Gegenstand aus. Zeigen Sie die Güte $2$. \lsg Zu zeigen: \[ \mathrm{OPT}(I) \;\le\; 2\,\mathrm{MGA}(I). \] Nummeriere nach Dichte, $p_1/w_1\ge\dots\ge p_n/w_n$, und sei $k+1$ der erste Gegenstand, den Greedy nicht mehr einpacken kann. \textbf{Schritt 1 (Relaxierung).} Erlaubt man, Gegenstände \emph{anteilig} einzupacken, wächst der Lösungsraum; das fraktionale Optimum $\mathrm{OPT}_f$ erfüllt daher $\mathrm{OPT}(I)\le\mathrm{OPT}_f(I)$. \textbf{Schritt 2 (fraktionales Optimum).} Die beste fraktionale Lösung füllt den Rucksack in Dichte-Reihenfolge: die Gegenstände $1,\dots,k$ ganz, vom Gegenstand $k+1$ einen Bruchteil $\le1$. Also $\mathrm{OPT}_f(I)\le p_1+\dots+p_k+p_{k+1}$. Da Greedy die Gegenstände $1,\dots,k$ ebenfalls einpackt, ist $p_1+\dots+p_k\le\mathrm{GA}(I)$, mithin \[ \mathrm{OPT}_f(I) \;\le\; \mathrm{GA}(I)+p_{k+1}. \] \textbf{Schritt 3 (Kombination).} Mit $p_{k+1}\le p_{\max}$ und $\mathrm{MGA}(I)=\max\{\mathrm{GA}(I),p_{\max}\}$ folgt \[ \mathrm{OPT}(I) \;\le\; \mathrm{GA}(I)+p_{\max} \;\le\; 2\max\{\mathrm{GA}(I),p_{\max}\} \;=\; 2\,\mathrm{MGA}(I). \] Somit hat ModifiedGreedy die Güte $2$. \aufg{Güte zeigen für Sahni} \problem{Knapsack} wie zuvor. \emph{Hinweis:} Sahni ($k$-Enumeration) probiert jede Vorauswahl von höchstens $k$ Gegenständen als festen Grundstock, füllt den Rest mit Greedy (Dichte-Reihenfolge) auf und gibt die beste gefundene Packung aus. Zeigen Sie die Güte $1+\frac1k$. \lsg Zu zeigen: \[ \mathrm{OPT}(I) \;\le\; \Bigl(1+\tfrac1k\Bigr)\,\mathrm{Sahni}(I). \] Sei $O$ eine optimale Auswahl mit Profit $\mathrm{OPT}(I)=p(O)$. \textbf{Fall $|O|\le k$.} Sahni probiert $O$ selbst als Vorauswahl. Also $\mathrm{Sahni}(I)\ge p(O)=\mathrm{OPT}(I)$. \textbf{Fall $|O|>k$.} Sei $H\subseteq O$ die Menge der $k$ profitreichsten Gegenstände aus $O$. Betrachte die Iteration mit Vorauswahl $H$. \begin{itemize} \item Greedy füllt mit den restlichen Gegenständen auf. Es verliert höchstens den ersten übersprungenen Gegenstand $o^\star \in O$: $\mathrm{Sahni}(I) \ge \mathrm{OPT}(I) - p_{o^\star}$. \item $o^\star$ und die $k$ Gegenstände aus $H$ sind $k+1$ Gegenstände aus $O$, jeder mit Profit $\ge p_{o^\star}$. Also $(k+1)\,p_{o^\star} \le \mathrm{OPT}(I)$, d.\,h.\ $p_{o^\star} \le \mathrm{OPT}(I)/(k+1)$. \end{itemize} Kombiniert: \[ \mathrm{Sahni}(I) \;\ge\; \mathrm{OPT}(I)-\frac{\mathrm{OPT}(I)}{k+1} \;=\; \frac{k}{k+1}\,\mathrm{OPT}(I), \] also $\mathrm{OPT}(I)\le(1+\tfrac1k)\,\mathrm{Sahni}(I)$. Somit hat Sahni die Güte $1+\frac1k$. \aufg{Güte widerlegen für Greedy} \problem{Knapsack} wie zuvor. \emph{Hinweis:} Greedy sortiert absteigend nach Profitdichte $p_i/w_i$ und packt jeden noch passenden Gegenstand ein. Zeigen Sie, dass Greedy keine konstante Güte hat: Für kein $c$ gilt $\mathrm{OPT}(I)\le c\cdot\mathrm{GA}(I)$ für alle Instanzen. \lsg Zu zeigen: Die Rate $\mathrm{OPT}(I)/\mathrm{GA}(I)$ ist unbeschränkt. \textbf{Instanzfamilie.} Für einen Parameter $B\ge2$ betrachte zwei Gegenstände mit Kapazität $B$: \[ (w_1,p_1)=(1,1), \qquad (w_2,p_2)=(B,\,B-1). \] Die Dichten sind $\frac{p_1}{w_1}=1$ und $\frac{p_2}{w_2}=\frac{B-1}{B}<1$. \textbf{Greedy.} Nach Dichte kommt der erste Gegenstand zuerst; er passt und wird eingepackt. Danach bleibt Restkapazität $B-1c\cdot\mathrm{GA}$. Somit besitzt Greedy keine konstante Güte. \aufg{Güte zeigen für $\Delta$TSP1} Metrisches TSP: vollständiger Graph mit symmetrischen Distanzen, die die Dreiecksungleichung $d(u,v)\le d(u,w)+d(w,v)$ erfüllen; gesucht eine kürzeste Rundreise. \emph{Hinweis ($\Delta$TSP1):} (1) MST $T$ berechnen; (2) alle MST-Kanten verdoppeln; (3) Eulerkreis; (4) Abkürzen (schon besuchte Knoten überspringen). Zeigen Sie die Güte $2$. \lsg Zu zeigen: \[ d(R) \;\le\; 2\,\mathrm{OPT}(I) \] für die berechnete Tour $R$, in drei Schritten. \textbf{Schritt 1 ($w(T)\le\mathrm{OPT}$).} Entfernt man aus einer optimalen Rundreise eine Kante, bleibt ein aufspannender Baum. Sein Gewicht ist $\le\mathrm{OPT}(I)$, und da $T$ ein \emph{minimaler} Spannbaum ist, gilt $w(T)\le\mathrm{OPT}(I)$. \textbf{Schritt 2 (Eulerkreis).} Durch das Verdoppeln haben alle Knoten geraden Grad, es existiert ein Eulerkreis. Er benutzt jede MST-Kante genau zweimal, hat also Länge \[ 2\,w(T) \;\le\; 2\,\mathrm{OPT}(I). \] \textbf{Schritt 3 (Abkürzen).} Beim Überspringen bereits besuchter Knoten wird eine Teilfolge $u\to w\to v$ durch die direkte Kante $u\to v$ ersetzt. Nach der Dreiecksungleichung ist $d(u,v)\le d(u,w)+d(w,v)$, das Abkürzen verlängert die Tour also nicht: \[ d(R) \;\le\; 2\,w(T) \;\le\; 2\,\mathrm{OPT}(I). \] Somit hat $\Delta$TSP1 die Güte $2$. \aufg{Güte zeigen für Christofides} Metrisches TSP wie zuvor. \emph{Hinweis ($\Delta$TSP2, Christofides):} (1) MST $T$; (2) $X=$ Knoten mit ungeradem Grad in $T$; (3) minimales perfektes Matching $M$ auf $X$; (4) Eulerkreis im Multigraphen $T+M$; (5) Abkürzen. Zeigen Sie die Güte $\frac32$. \lsg Zu zeigen: \[ d(R) \;\le\; \tfrac32\,\mathrm{OPT}(I). \] \textbf{Schritt 1 ($w(T)\le\mathrm{OPT}$).} Wie bei $\Delta$TSP1: Entfernt man aus einer optimalen Rundreise eine Kante, entsteht ein Spannbaum; sein Gewicht ist $\le\mathrm{OPT}(I)$, und da $T$ ein minimaler Spannbaum ist, gilt $w(T)\le\mathrm{OPT}(I)$. \textbf{Schritt 2 ($w(M)\le\mathrm{OPT}/2$).} Die Zahl $|X|$ der ungerad-gradigen Knoten ist gerade. Kürzt man eine optimale Rundreise auf die Knoten aus $X$ ab (alle übrigen überspringen), so entsteht nach der Dreiecksungleichung ein Kreis $C$ auf $X$ mit $d(C)\le\mathrm{OPT}(I)$. Ein Kreis über die gerade Knotenzahl $|X|$ zerfällt in zwei disjunkte perfekte Matchings $M_1,M_2$ (die abwechselnden Kanten). Wegen $w(M_1)+w(M_2)=d(C)\le\mathrm{OPT}(I)$ ist das billigere höchstens $\mathrm{OPT}(I)/2$, und das minimale perfekte Matching erfüllt \[ w(M) \;\le\; \min\{w(M_1),w(M_2)\} \;\le\; \tfrac12\,\mathrm{OPT}(I). \] \textbf{Schritt 3 (Eulerkreis und Abkürzen).} In $T+M$ hat jeder Knoten geraden Grad, es existiert ein Eulerkreis der Länge $w(T)+w(M)$. Das Abkürzen verlängert wegen der Dreiecksungleichung nicht, also \[ d(R) \;\le\; w(T)+w(M) \;\le\; \mathrm{OPT}(I)+\tfrac12\,\mathrm{OPT}(I) \;=\; \tfrac32\,\mathrm{OPT}(I). \] Somit hat Christofides die Güte $\frac32$. \aufg{Güte zeigen für 2ApproxVC} \problem{VertexCover}: kleinste Knotenmenge $C$, die jede Kante abdeckt. \emph{Hinweis:} 2ApproxVC durchläuft alle Kanten; sind beide Endpunkte noch nicht in $C$, werden \emph{beide} zu $C$ hinzugefügt. Zeigen Sie die Güte $2$. \lsg Zu zeigen: \[ |C| \;\le\; 2\,|C^\ast| \] für ein minimales Vertex Cover $C^\ast$. Sei $A$ die Menge der Kanten, bei denen beide Endpunkte aufgenommen wurden; dann ist $|C|=2|A|$. \textbf{$A$ ist ein Matching.} Hätten zwei Kanten aus $A$ einen gemeinsamen Endpunkt, so wäre bei der später betrachteten dieser Endpunkt bereits in $C$ gewesen -- sie wäre nicht aufgenommen worden. Also sind die Kanten aus $A$ paarweise knotendisjunkt. \textbf{Schranke für das Optimum.} $C^\ast$ deckt jede Kante aus $A$ mit mindestens einem Endpunkt ab; da die Kanten aus $A$ knotendisjunkt sind, braucht jede einen \emph{eigenen} Knoten, also $|C^\ast|\ge|A|$. \textbf{Kombination.} \[ |C| \;=\; 2|A| \;\le\; 2|C^\ast|. \] Somit hat 2ApproxVC die Güte $2$. \aufg{Güte zeigen für MAX-3-SAT} \problem{MAX-3-SAT}: Formel $\varphi$ in KNF mit drei Literalen pro Klausel; gesucht eine Belegung, die die Anzahl $v(\cdot)$ der erfüllten Klauseln maximiert. \emph{Hinweis:} Algorithmus $A$ wertet $\beta_0$ (alle \false) und $\beta_1$ (alle \true) aus und gibt die bessere Belegung zurück. Zeigen Sie die Güte $2$. \lsg Zu zeigen: \[ v(A(\varphi)) \;\ge\; \tfrac12\,v(\mathrm{OPT}(\varphi)). \] Sei $\varphi$ eine Formel mit $m$ Klauseln. \textbf{Jede Klausel zählt einmal.} Unter $\beta_0$ ist jedes negative Literal wahr, unter $\beta_1$ jedes positive. Da jede Klausel mindestens ein Literal enthält und jedes Literal positiv oder negativ ist, wird jede Klausel von $\beta_0$ oder von $\beta_1$ erfüllt. Somit \[ v(\beta_0)+v(\beta_1) \;\ge\; m . \] \textbf{Obere Schranke für das Optimum.} Es können höchstens alle $m$ Klauseln erfüllt sein, also $v(\mathrm{OPT}(\varphi))\le m$. \textbf{Kombination.} $A$ wählt die bessere der beiden Belegungen, daher \[ v(A(\varphi)) \;=\; \max\{v(\beta_0),v(\beta_1)\} \;\ge\; \frac{v(\beta_0)+v(\beta_1)}{2} \;\ge\; \frac m2 \;\ge\; \frac{v(\mathrm{OPT}(\varphi))}{2}. \] Somit hat $A$ die Güte $2$. \aufg{Güte zeigen für ApproximateSubsetSum} \problem{ApproximateSubsetSum}: Zahlen $a_1,\dots,a_n\le T$ mit $\sum_i a_i>T$; maximiere $\sum_{j\in S}a_j$ unter $\sum_{j\in S}a_j\le T$. \emph{Hinweis:} GA sortiert absteigend, nimmt der Reihe nach jedes noch passende Element und \emph{stoppt} beim ersten nicht mehr passenden. Zeigen Sie die Güte $2$. \lsg Zu zeigen: \[ \mathrm{GA}(I) \;\ge\; \tfrac12\,\mathrm{OPT}(I). \] Sei $a_\ell$ das erste Element, das nicht mehr passte; es existiert wegen $\sum_i a_i>T$. \textbf{Überlauf-Schranke.} Zum Stoppzeitpunkt hätte $a_\ell$ die Kapazität überschritten: \[ \mathrm{GA}(I)+a_\ell \;>\; T \;\ge\; \mathrm{OPT}(I). \] \textbf{Größe des gestoppten Elements.} Wegen der absteigenden Sortierung ist jedes bereits gewählte Element $\ge a_\ell$, also enthält die GA-Auswahl ein Element $a_j\ge a_\ell$ und damit $\mathrm{GA}(I)\ge a_\ell$. \textbf{Kombination.} Einsetzen liefert \[ 2\,\mathrm{GA}(I) \;\ge\; \mathrm{GA}(I)+a_\ell \;>\; T \;\ge\; \mathrm{OPT}(I), \] also $\mathrm{GA}(I)\ge\mathrm{OPT}(I)/2$. Somit hat GA die Güte $2$. \aufg{Güte zeigen für Strip Packing: NFDH} \problem{StripPacking}: Rechtecke mit Höhen $h(r_i)\le1$, absteigend nach Höhe sortiert, in einen Streifen der Breite $1$ packen und die Höhe minimieren. \emph{Hinweis:} NFDH packt stufenweise von links; passt ein Rechteck nicht mehr, beginnt eine neue Stufe (deren Höhe die ihres ersten, also höchsten Rechtecks ist). Zeigen Sie $\mathrm{NFDH}(L)\le 2\,\mathrm{OPT}(L)+h_{\max}$. \lsg Zu zeigen: \[ \mathrm{NFDH}(L) \;\le\; 2\,\mathrm{OPT}(L)+h_{\max}. \] Sei $H_i$ die Höhe der Stufe $i$ (Höhe ihres ersten Rechtecks), $W_i$ ihre belegte Gesamtbreite und $A_i$ ihre Rechteck-Gesamtfläche. \textbf{Erstens (Fläche einer Stufe).} Jedes Rechteck der Stufe $i$ hat wegen der absteigenden Sortierung Höhe $\ge H_{i+1}$; die Rechtecke der Stufe $i$ haben zusammen Breite $W_i$, also \[ A_i \;\ge\; W_i\,H_{i+1}. \] \textbf{Zweitens (das überlaufende Rechteck).} Das erste Rechteck der Stufe $i{+}1$ passte nicht mehr auf Stufe $i$, hat also Breite $>1-W_i$ und Höhe $H_{i+1}$, mithin Fläche $>(1-W_i)\,H_{i+1}$. \textbf{Kombination.} Zerlege $H_{i+1}$ und setze beide Schranken ein: \[ H_{i+1} \;=\; W_i H_{i+1}+(1-W_i)H_{i+1} \;<\; A_i + \bigl(\text{Fläche des ersten Rechtecks von Stufe } i{+}1\bigr). \] \textbf{Summierung.} Summation über $i\ge1$; dabei zählt jede Stufe höchstens zweimal (einmal als $A_i$, einmal über ihr erstes Rechteck), und die Gesamtfläche passt in einen Streifen der Breite $1$, also $\text{Gesamtfläche}\le\mathrm{OPT}(L)$: \[ \sum_{i\ge2} H_i \;<\; 2\cdot\text{Gesamtfläche} \;\le\; 2\,\mathrm{OPT}(L). \] \textbf{Fazit.} Die erste Stufe hat Höhe $H_1=h_{\max}$. Damit \[ \mathrm{NFDH}(L) \;=\; \sum_i H_i \;\le\; 2\,\mathrm{OPT}(L)+h_{\max}. \] Somit gilt die behauptete Schranke. \clearpage \section{ETH} % ================================================================== \aufg{ETH-Schranke zeigen für VertexCover} \textbf{Problem \problem{VertexCover}:}\\ \textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k$.\\ \textbf{Entscheide:} Gibt es $S \subseteq V$ mit $|S| \le k$, sodass $v \in S$ oder $u \in S$ für jede Kante $\{v,u\} \in E$? Betrachten Sie die Reduktion $\problem{Clique} \redp \problem{VertexCover}$. Aus $(G = (V,E), k)$ wird die Instanz $(G' = (V, \bar E), k')$ mit: \begin{itemize} \item $\bar E = \{\{v,u\} \mid v \ne u,\ \{v,u\} \notin E\}$ \item $k' = |V| - k$ \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|V'|$, $|E'|$ und $k'$ der VC-Instanz in Abhängigkeit der Clique-Instanz an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{VertexCover} bzgl.\ $|V'|$, $|E'|$ und $k'$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{Clique} nicht in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|V'| = |V|$, \quad $|E'| = \tfrac12|V|(|V|-1) - |E| \le |V|^2$, \quad $k' = |V| - k \le |V|$. \textbf{b)} \textbf{Bzgl.\ $|V'|$:} \begin{itemize} \item Angenommen, \problem{VertexCover} wäre in $2^{o(|V'|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|V'| = |V|$ wird daraus ein $2^{o(|V|)} \cdot |I|^{O(1)}$-Algorithmus für \problem{Clique}. \item Widerspruch zur ETH. \end{itemize} \textbf{Bzgl.\ $|E'|$:} \begin{itemize} \item Angenommen, \problem{VertexCover} wäre in $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|E'| \le |V|^2$ ist $\sqrt{|E'|} \le |V|$, also $\sqrt{|E'|} = O(|V|)$. \item Daraus wird ein $2^{o(|V|)}$-Algorithmus für \problem{Clique}. \item Widerspruch zur ETH. \end{itemize} \textbf{Bzgl.\ $k'$:} \begin{itemize} \item Angenommen, \problem{VertexCover} wäre in $2^{o(k')} \cdot |I|^{O(1)}$ lösbar. \item Wegen $k' \le |V|$ wird daraus ein $2^{o(|V|)}$-Algorithmus für \problem{Clique}. \item Widerspruch zur ETH. \end{itemize} Bounds: kein $2^{o(|V'|)}$, kein $2^{o(\sqrt{|E'|})}$, kein $2^{o(k')}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für HittingSet} \textbf{Problem \problem{HittingSet}:}\\ \textbf{Gegeben:} Eine Menge $U$, Teilmengen $F_1, \dots, F_r \subseteq U$ und eine Zahl $k$.\\ \textbf{Entscheide:} Gibt es $S \subseteq U$ mit $|S| \le k$ und $S \cap F_i \ne \emptyset$ für alle $i \in [r]$? Betrachten Sie die Reduktion $\problem{3-SAT} \redp \problem{HittingSet}$. Aus einer 3-SAT-Instanz mit Variablen $x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ wird: \begin{itemize} \item $U = \{x_i, \bar x_i \mid i \in [n]\}$ \item $F_i = \{x_i, \bar x_i\}$ für jede Variable $i \in [n]$ \item $F_{n+j} = C_j$ für jede Klausel $j \in [m]$ \item $k = n$ \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|U|$, die Mengenzahl $r$ und $k$ in Abhängigkeit von $n$ und $m$ an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{HittingSet} bzgl.\ $|U|$, $r$ und $k$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{3-SAT} nicht in $2^{o(n)} \cdot |I|^{O(1)}$ lösbar, mit dem Sparsification-Lemma auch nicht in $2^{o(m)} \cdot |I|^{O(1)}$. \lsg \textbf{a)} $|U| = 2n$, \quad $r = n + m$, \quad $k = n$. \textbf{b)} \textbf{Bzgl.\ $|U|$:} \begin{itemize} \item Angenommen, \problem{HittingSet} wäre in $2^{o(|U|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|U| = 2n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}. \item Direkter Widerspruch zur ETH. \end{itemize} \textbf{Bzgl.\ $r$:} \begin{itemize} \item Angenommen, \problem{HittingSet} wäre in $2^{o(r)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $r = n + m$ und $n \le 3m$ ist $r = O(m)$. \item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} \textbf{Bzgl.\ $k$:} \begin{itemize} \item Angenommen, \problem{HittingSet} wäre in $2^{o(k)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $k = n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}. \item Direkter Widerspruch zur ETH. \end{itemize} Bounds: kein $2^{o(|U|)}$, kein $2^{o(r)}$, kein $2^{o(k)}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für $k$-Clique} \textbf{Problem $k$-\problem{Clique}:}\\ \textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k \ge 1$.\\ \textbf{Entscheide:} Gibt es eine Clique $C \subseteq V$ mit $|C| \ge k$, d.h.\ $\{v,u\} \in E$ für alle $v, u \in C$ mit $v \ne u$? Betrachten Sie die Reduktion $\problem{3-SAT} \redp k\text{-}\problem{Clique}$. Aus einer 3-SAT-Instanz mit Klauseln $F_1, \dots, F_m$ wird ($y_{ij}$ sei das $j$-te Literal der Klausel $i$): \begin{itemize} \item $V = \{[i,j] \mid \text{$j$-tes Literal in Klausel } i\}$ \item $E = \{\{[i,j],[i',j']\} \mid i \ne i',\ y_{ij} \ne \neg y_{i'j'}\}$ \item $k = m$ \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|V|$, $|E|$ und $k$ der Clique-Instanz in Abhängigkeit von $n$ und $m$ an. \item[b)] Beweisen Sie die ETH-Schranken für $k$-\problem{Clique} bzgl.\ $|V|$, $|E|$ und $k$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|V| = O(m)$ (je Klausel $\le 3$ Literale), \quad $|E| = O(m^2)$, \quad $k = m$. \textbf{b)} \textbf{Bzgl.\ $|V|$:} \begin{itemize} \item Angenommen, $k$-\problem{Clique} wäre in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|V| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} \textbf{Bzgl.\ $|E|$:} \begin{itemize} \item Angenommen, $k$-\problem{Clique} wäre in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|E| = O(m^2)$ ist $\sqrt{|E|} = O(m)$. \item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} \textbf{Bzgl.\ $k$:} \begin{itemize} \item Angenommen, $k$-\problem{Clique} wäre in $2^{o(k)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $k = m$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} Bounds: kein $2^{o(|V|)}$, kein $2^{o(\sqrt{|E|})}$, kein $2^{o(k)}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für $k$-IndependentSet} \textbf{Problem $k$-\problem{IS}:}\\ \textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k$.\\ \textbf{Entscheide:} Gibt es $S \subseteq V$ mit $|S| \ge k$, sodass $\{v,u\} \notin E$ für alle $v, u \in S$ mit $v \ne u$? Betrachten Sie die Reduktion $k\text{-}\problem{Clique} \redp k\text{-}\problem{IS}$. Aus $(G = (V,E), k)$ wird die Instanz $(G' = (V, \bar E), k')$ mit: \begin{itemize} \item $\bar E = \{\{v,u\} \mid v \ne u,\ \{v,u\} \notin E\}$ \item $k' = k$ \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|V'|$, $|E'|$ und $k'$ der IS-Instanz in Abhängigkeit der Clique-Instanz an. \item[b)] Beweisen Sie die ETH-Schranken für $k$-\problem{IS} bzgl.\ $|V'|$, $|E'|$ und $k'$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist $k$-\problem{Clique} weder in $2^{o(|V|)} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ noch in $2^{o(k)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|V'| = |V|$, \quad $|E'| = \tfrac12|V|(|V|-1) - |E| \le |V|^2$, \quad $k' = k$. \textbf{b)} \textbf{Bzgl.\ $|V'|$:} \begin{itemize} \item Angenommen, $k$-\problem{IS} wäre in $2^{o(|V'|)} \cdot |I|^{O(1)}$ lösbar. \item Ein unabhängiges Set in $\bar G$ ist eine Clique in $G$; via Komplementbildung löst der Algorithmus \problem{Clique}. \item Wegen $|V'| = |V|$ wird daraus ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $|E'|$:} \begin{itemize} \item Angenommen, $k$-\problem{IS} wäre in $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|E'| \le |V|^2$ ist $\sqrt{|E'|} = O(|V|)$. \item Via Komplementbildung wird daraus ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $k'$:} \begin{itemize} \item Angenommen, $k$-\problem{IS} wäre in $2^{o(k')} \cdot |I|^{O(1)}$ lösbar. \item Wegen $k' = k$ wird daraus ein $2^{o(k)}$-Algorithmus für $k$-\problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(|V'|)}$, kein $2^{o(\sqrt{|E'|})}$, kein $2^{o(k')}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für 3-DM} \textbf{Problem \problem{3-DM}:}\\ \textbf{Gegeben:} Mengen $U, V, W$ mit $|U| = |V| = |W|$ und eine Tripelmenge $T \subseteq U \times V \times W$.\\ \textbf{Entscheide:} Gibt es $M \subseteq T$ mit $|M| = |U|$, sodass je zwei verschiedene Tripel aus $M$ in allen drei Koordinaten verschieden sind? Betrachten Sie die Reduktion $\problem{SAT} \redp \problem{3-DM}$ (Vorlesung), angewandt auf 3-SAT-Instanzen: Sie erzeugt drei gleich große Grundmengen mit $|U| = |V| = |W| = O(m^2)$ und eine Tripelmenge mit $|T| = O(m^4)$. Beweisen Sie die ETH-Schranken für \problem{3-DM} bzgl.\ $|U|$ und $|T|$ basierend auf der Reduktion. \emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{Bzgl.\ $|U|$:} \begin{itemize} \item Angenommen, \problem{3-DM} wäre in $2^{o(\sqrt{|U|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|U| = O(m^2)$ ist $\sqrt{|U|} = O(m)$. \item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} \textbf{Bzgl.\ $|T|$:} \begin{itemize} \item Angenommen, \problem{3-DM} wäre in $2^{o(\sqrt[4]{|T|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|T| = O(m^4)$ ist $\sqrt[4]{|T|} = O(m)$. \item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} Bounds: kein $2^{o(\sqrt{|U|})}$, kein $2^{o(\sqrt[4]{|T|})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für 3-ExactCover} \textbf{Problem \problem{3-EC}:}\\ \textbf{Gegeben:} Eine Grundmenge $U$ und eine Familie $F = \{S_1, \dots, S_n\}$ von Teilmengen mit $|S_j| = 3$ für alle $j$.\\ \textbf{Entscheide:} Gibt es eine Teilfamilie $F' \subseteq F$, deren Mengen paarweise disjunkt sind und $U$ überdecken ($\bigcup_{S \in F'} S = U$)? Betrachten Sie die Reduktion $\problem{3-DM} \redp \problem{3-EC}$: \problem{3-DM} ist ein Spezialfall von \problem{3-EC}. Eine 3-DM-Instanz mit Tripelmenge $T$ wird direkt zur 3-EC-Instanz mit: \begin{itemize} \item Grundmenge $U$ = Vereinigung der drei 3-DM-Mengen \item $F = \{\{v,w,u\} \mid (v,w,u) \in T\}$ \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|U|$ und die Zahl der Mengen $|F|$ der 3-EC-Instanz in Abhängigkeit der 3-DM-Instanz an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{3-EC} bzgl.\ $|U|$ und $|F|$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{3-DM} weder in $2^{o(\sqrt{|V|})} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt[4]{|T|})} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|U| = O(|V|)$, \quad $|F| = |T|$. \textbf{b)} \textbf{Bzgl.\ $|U|$:} \begin{itemize} \item Angenommen, \problem{3-EC} wäre in $2^{o(\sqrt{|U|})} \cdot |I|^{O(1)}$ lösbar. \item Jede \problem{3-DM}-Instanz ist eine \problem{3-EC}-Instanz mit $|U| = O(|V|)$, also $\sqrt{|U|} = O(\sqrt{|V|})$. \item Daraus wird ein $2^{o(\sqrt{|V|})}$-Algorithmus für \problem{3-DM}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $|F|$:} \begin{itemize} \item Angenommen, \problem{3-EC} wäre in $2^{o(\sqrt[4]{|F|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|F| = |T|$ löst der Algorithmus jede \problem{3-DM}-Instanz. \item Daraus wird ein $2^{o(\sqrt[4]{|T|})}$-Algorithmus für \problem{3-DM}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(\sqrt{|U|})}$, kein $2^{o(\sqrt[4]{|F|})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für SubsetSum} \textbf{Problem \problem{SubsetSum}:}\\ \textbf{Gegeben:} Zahlen $c_1, \dots, c_n$ und ein Zielwert $K$.\\ \textbf{Entscheide:} Gibt es $S \subseteq \{1, \dots, n\}$ mit $\sum_{j \in S} c_j = K$? Betrachten Sie die Reduktion $\problem{3-EC} \redp \problem{SubsetSum}$: Jede Menge $S_j \in F$ der 3-EC-Instanz liefert ein Item $c_j$ (Bitvektor über $U$), also $n = |F|$ Items. \begin{enumerate} \item[a)] Geben Sie die Itemzahl $n$ der SubsetSum-Instanz in Abhängigkeit der 3-EC-Instanz an. \item[b)] Beweisen Sie die ETH-Schranke für \problem{SubsetSum} bzgl.\ $n$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{3-EC} nicht in $2^{o(\sqrt[4]{|F|})} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $n = |F|$. \textbf{b)} \textbf{Bzgl.\ $n$:} \begin{itemize} \item Angenommen, \problem{SubsetSum} wäre in $2^{o(\sqrt[4]{n})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $n = |F|$ wird daraus ein $2^{o(\sqrt[4]{|F|})}$-Algorithmus für \problem{3-EC}. \item Widerspruch zum Hinweis. \end{itemize} Bound: kein $2^{o(\sqrt[4]{n})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für $k$-Color} \textbf{Problem $k$-\problem{Color}:}\\ \textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k \ge 1$.\\ \textbf{Entscheide:} Gibt es eine Färbung $f : V \to [k]$ mit $f(v) \ne f(u)$ für alle $\{v,u\} \in E$? Betrachten Sie die Reduktion $\problem{3-SAT} \redp k\text{-}\problem{Color}$ mit: \begin{itemize} \item $V = \{x_i, \bar x_i, v_i \mid i \in [n]\} \cup \{C_j \mid j \in [m]\} \cup \{z\}$ \item $E$: die Kanten des Vorlesungs-Gadgets \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|V|$ und $|E|$ der Color-Instanz in Abhängigkeit von $n$ und $m$ an. \item[b)] Beweisen Sie die ETH-Schranken für $k$-\problem{Color} bzgl.\ $|V|$ und $|E|$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|V| = 3n + m + 1$; wegen $n \le 3m$ also $|V| = O(m)$. \quad $|E| = O(n^2 + nm + m) = O(m^2)$. \textbf{b)} \textbf{Bzgl.\ $|V|$:} \begin{itemize} \item Angenommen, $k$-\problem{Color} wäre in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|V| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} \textbf{Bzgl.\ $|E|$:} \begin{itemize} \item Angenommen, $k$-\problem{Color} wäre in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|E| = O(m^2)$ ist $\sqrt{|E|} = O(m)$. \item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} Bounds: kein $2^{o(|V|)}$, kein $2^{o(\sqrt{|E|})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für CoverClique} \textbf{Problem \problem{CoverClique}:}\\ \textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k \in \mathbb{N}_{\ge 1}$.\\ \textbf{Entscheide:} Existieren $k$ paarweise disjunkte Cliquen $C_1, \dots, C_k \subseteq V$, die alle Knoten überdecken? Betrachten Sie die Reduktion $k\text{-}\problem{Color} \redp \problem{CoverClique}$. Aus $(G = (V,E), k)$ wird die Instanz $(G' = (V, \bar E), k)$ mit $\bar E = \{\{v,u\} \mid v \ne u,\ \{v,u\} \notin E\}$. \begin{enumerate} \item[a)] Geben Sie $|V'|$ und $|\bar E|$ der CoverClique-Instanz in Abhängigkeit der Color-Instanz an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{CoverClique} bzgl.\ $|V'|$ und $|\bar E|$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist $k$-\problem{Color} nicht in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|V'| = |V|$, \quad $|\bar E| = \tfrac12|V|(|V|-1) - |E| \le |V|^2$. \textbf{b)} \textbf{Bzgl.\ $|V'|$:} \begin{itemize} \item Angenommen, \problem{CoverClique} wäre in $2^{o(|V'|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|V'| = |V|$ wird daraus ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Color}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $|\bar E|$:} \begin{itemize} \item Angenommen, \problem{CoverClique} wäre in $2^{o(\sqrt{|\bar E|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|\bar E| \le |V|^2$ ist $\sqrt{|\bar E|} = O(|V|)$. \item Daraus wird ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Color}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(|V'|)}$, kein $2^{o(\sqrt{|\bar E|})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für $\Delta$Cover} \textbf{Problem $\Delta$\problem{Cover}:}\\ \textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und $k \in \mathbb{N}_0$.\\ \textbf{Entscheide:} Gibt es $C_\Delta \subseteq V$ mit $|C_\Delta| \le k$, sodass $\{v,u,w\} \cap C_\Delta \ne \emptyset$ für jedes Dreieck $\{v,u,w\}$ (also $\{v,u\},\{v,w\},\{u,w\} \in E$) gilt? Reduktion $\problem{VertexCover} \redp \Delta\problem{Cover}$: Aus $(G = (V,E), k)$ wird $(G' = (V',E'), k)$ mit \begin{itemize} \item $V' = V \cup \{v_e \mid e \in E\}$, \item $E' = E \cup \{\{v_e, e_1\}, \{v_e, e_2\} \mid e = \{e_1, e_2\} \in E\}$ (je Kante ein aufgesetztes Dreieck), \item $k$ unverändert. \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|V'|$ und $|E'|$ der $\Delta$Cover-Instanz in Abhängigkeit der VC-Instanz an. \item[b)] Beweisen Sie die ETH-Schranken für $\Delta\problem{Cover}$ bzgl.\ $|V'|$ und $|E'|$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{VertexCover} weder in $2^{o(|V|)} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|V'| = |V| + |E|$, \quad $|E'| = |E| + 2|E| = 3|E|$. \textbf{b)} \textbf{Bzgl.\ $|V'|$:} \begin{itemize} \item Angenommen, $\Delta\problem{Cover}$ wäre in $2^{o(\sqrt{|V'|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|V'| = |V| + |E| \le |V| + |V|^2 = O(|V|^2)$ ist $\sqrt{|V'|} = O(|V|)$. \item Daraus wird ein $2^{o(|V|)}$-Algorithmus für \problem{VertexCover}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $|E'|$:} \begin{itemize} \item Angenommen, $\Delta\problem{Cover}$ wäre in $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|E'| = 3|E| = O(|E|)$ ist $\sqrt{|E'|} = O(\sqrt{|E|})$. \item Daraus wird ein $2^{o(\sqrt{|E|})}$-Algorithmus für \problem{VertexCover}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(\sqrt{|V'|})}$, kein $2^{o(\sqrt{|E'|})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für NAE-4-SAT} \textbf{Problem \problem{NAE-4-SAT}:}\\ \textbf{Gegeben:} Variablen $x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ mit $|C_i| \le 4$ für alle $i \in [m]$.\\ \textbf{Entscheide:} Gibt es eine Belegung $\varphi$, sodass jede Klausel $C_i$ zwei Literale $y, z \in C_i$ mit $\varphi(y) \ne \varphi(z)$ enthält? Reduktion $\problem{3-SAT} \redp \problem{NAE-4-SAT}$: Aus Variablen $x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ wird \begin{itemize} \item die Variablenmenge $\{x_1, \dots, x_n, w\}$ mit frischer Variable $w$, \item pro Klausel $C_i$ die NAE-Klausel $C_i \cup \{w\}$. \end{itemize} \begin{enumerate} \item[a)] Geben Sie die Variablenzahl $n'$ und die Klauselzahl $m'$ der NAE-4-SAT-Instanz in Abhängigkeit von $n$ und $m$ an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{NAE-4-SAT} bzgl.\ $n'$ und $m'$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{3-SAT} nicht in $2^{o(n)} \cdot |I|^{O(1)}$ lösbar, mit dem Sparsification-Lemma auch nicht in $2^{o(m)} \cdot |I|^{O(1)}$. \lsg \textbf{a)} $n' = n + 1$, \quad $m' = m$. \textbf{b)} \textbf{Bzgl.\ $n'$:} \begin{itemize} \item Angenommen, \problem{NAE-4-SAT} wäre in $2^{o(n')} \cdot |I|^{O(1)}$ lösbar. \item Wegen $n' = n + 1$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}. \item Direkter Widerspruch zur ETH. \end{itemize} \textbf{Bzgl.\ $m'$:} \begin{itemize} \item Angenommen, \problem{NAE-4-SAT} wäre in $2^{o(m')} \cdot |I|^{O(1)}$ lösbar. \item Wegen $m' = m$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} Bounds: kein $2^{o(n')}$, kein $2^{o(m')}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für SetSplitting} \textbf{Problem \problem{SetSplitting}:}\\ \textbf{Gegeben:} Eine Grundmenge $S$ und Teilmengen $F_1, \dots, F_r \subseteq S$.\\ \textbf{Entscheide:} Gibt es eine Partition $S = S_1 \mathbin{\dot\cup} S_2$ mit $F_i \cap S_1 \ne \emptyset \ne F_i \cap S_2$ für alle $i \in [r]$? Reduktion $\problem{NAE-4-SAT} \redp \problem{SetSplitting}$: Aus $n$ Variablen $x_1, \dots, x_n$ und $m$ Klauseln $C_1, \dots, C_m$ wird \begin{itemize} \item die Grundmenge $S = \{x_i, \bar x_i \mid i \in [n]\}$, \item pro Variable $i \in [n]$ die Teilmenge $\{x_i, \bar x_i\} \subseteq S$, \item pro Klausel $C_i$ die Teilmenge $C_i \subseteq S$. \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|S|$ und die Mengenzahl $r$ der SetSplitting-Instanz in Abhängigkeit von $n$ und $m$ an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{SetSplitting} bzgl.\ $|S|$ und $r$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} \problem{NAE-4-SAT} ist unter der ETH weder in $2^{o(n)} \cdot |I|^{O(1)}$ noch in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|S| = 2n$, \quad $r = n + m$. \textbf{b)} \textbf{Bzgl.\ $|S|$:} \begin{itemize} \item Angenommen, \problem{SetSplitting} wäre in $2^{o(|S|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|S| = 2n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{NAE-4-SAT}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $r$:} \begin{itemize} \item Angenommen, \problem{SetSplitting} wäre in $2^{o(r)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $\le 4$ Literalen je Klausel ist $n \le 4m + 1$, also $r = n + m = O(m)$. \item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{NAE-4-SAT}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(|S|)}$, kein $2^{o(r)}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für DominatingSet} \textbf{Problem \problem{DominatingSet}:}\\ \textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und $k \in \mathbb{N}_{\ge 1}$.\\ \textbf{Entscheide:} Gibt es eine Menge $M \subseteq V$ mit $|M| \le k$, sodass jeder Knoten $v \in V$ in $M$ liegt oder zu einem Knoten in $M$ benachbart ist? Reduktion $\problem{3-SAT} \redp \problem{DominatingSet}$: Aus Variablen $x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ wird \begin{itemize} \item pro Variable $x_i$ die Knoten $x_i, \bar x_i, d_i$ mit den Dreieckskanten $\{x_i, \bar x_i\}, \{x_i, d_i\}, \{d_i, \bar x_i\}$, \item pro Klausel $C_j$ ein Knoten $C_j$ mit Kanten $\{C_j, \ell\}$ zu jedem Literal $\ell \in C_j$. \end{itemize} \begin{enumerate} \item[a)] Geben Sie $|V|$ und $|E|$ der DominatingSet-Instanz in Abhängigkeit von $n$ und $m$ an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{DominatingSet} bzgl.\ $|V|$ und $|E|$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|V| = 3n + m$; wegen $n \le 3m$ also $|V| = O(m)$. \quad $|E| = 3n + 3m = O(m)$ (linear in $m$). \textbf{b)} \textbf{Bzgl.\ $|V|$:} \begin{itemize} \item Angenommen, \problem{DominatingSet} wäre in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|V| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} \textbf{Bzgl.\ $|E|$:} \begin{itemize} \item Angenommen, \problem{DominatingSet} wäre in $2^{o(|E|)} \cdot |I|^{O(1)}$ lösbar (ohne Wurzel, da $|E|$ nur linear wächst). \item Wegen $|E| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} Bounds: kein $2^{o(|V|)}$, kein $2^{o(|E|)}$ (ohne Wurzel). \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für GridTiling} \textbf{Problem \problem{GridTiling}:}\\ \textbf{Gegeben:} Zahlen $k, N \in \mathbb{N}$ und je $(i,j) \in [k]^2$ eine Menge $S_{i,j} \subseteq [N]^2$.\\ \textbf{Entscheide:} Gibt es Tupel $(e_{i,j})_{(i,j) \in [k]^2}$ mit $e_{i,j} \in S_{i,j}$, sodass für $e_{i,j} = (a,b)$, $e_{i,j+1} = (a',b')$ stets $a = a'$ und für $e_{i,j} = (a,b)$, $e_{i+1,j} = (a',b')$ stets $b = b'$ gilt? Reduktion $\problem{Clique} \redp \problem{GridTiling}$ mit $N := |V|$ und $c \cdot N \le k \le N$: Aus $(G = (V,E), k)$ mit $V = \{1, \dots, N\}$ ohne isolierte Knoten wird \begin{itemize} \item $S_{i,i} = \{(a,a) \mid a \in V\}$ (Diagonale), \item $S_{i,j} = \{(a,b) \mid a \ne b,\ \{a,b\} \in E\}$ für $i \ne j$, \item $k$ unverändert. \end{itemize} \begin{enumerate} \item[a)] Geben Sie $X = \sum_{(i,j)} |S_{i,j}|$ und $Y = \max_{(i,j)} |S_{i,j}|$ in Abhängigkeit von $N$ an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{GridTiling} bzgl.\ $X$ und $Y$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{Clique} nicht in $2^{o(N)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $|S_{i,i}| = N$, $|S_{i,j}| = 2|E| \le N^2$ und $k = \Theta(N)$, also $X \le k \cdot N + k^2 \cdot N^2 = O(N^4)$ und $Y \le \max(N, N^2) = O(N^2)$. \textbf{b)} \textbf{Bzgl.\ $X$:} \begin{itemize} \item Angenommen, \problem{GridTiling} wäre in $2^{o(\sqrt[4]{X})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $X = O(N^4)$ ist $\sqrt[4]{X} = O(N)$. \item Daraus wird ein $2^{o(N)}$-Algorithmus für \problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $Y$:} \begin{itemize} \item Angenommen, \problem{GridTiling} wäre in $2^{o(\sqrt{Y})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $Y = O(N^2)$ ist $\sqrt{Y} = O(N)$. \item Daraus wird ein $2^{o(N)}$-Algorithmus für \problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(\sqrt[4]{X})}$, kein $2^{o(\sqrt{Y})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für SetCover} \textbf{Problem \problem{SetCover}:}\\ \textbf{Gegeben:} Eine Menge $U$, Teilmengen $F_1, \dots, F_r \subseteq U$ und $k \in \mathbb{N}$.\\ \textbf{Entscheide:} Gibt es $S \subseteq \{1, \dots, r\}$ mit $|S| \le k$ und $\bigcup_{i \in S} F_i = U$? Reduktion $\problem{SetCover} \redp \problem{HittingSet}$ (Rollentausch, involutorisch): Aus $(U, F_1, \dots, F_r, k)$ wird \begin{itemize} \item die Grundmenge $U' = \{1, \dots, r\}$ (ein Element je Menge $F_i$), \item pro $w \in U$ die Menge $F'_w = \{v \mid w \in F_v\}$, \item $k' = k$. \end{itemize} \begin{enumerate} \item[a)] Geben Sie die Mengenzahl $r'$ und die Elementzahl $|U'|$ der erzeugten HittingSet-Instanz in Abhängigkeit der SetCover-Instanz an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{SetCover} bzgl.\ $|U|$ und $r$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{HittingSet} weder in $2^{o(r')} \cdot |I|^{O(1)}$ noch in $2^{o(|U'|)} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} $r' = |U|$, \quad $|U'| = r$ (der Rollentausch ist involutorisch). \textbf{b)} \textbf{Bzgl.\ $|U|$:} \begin{itemize} \item Angenommen, \problem{SetCover} wäre in $2^{o(|U|)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $r' = |U|$ wird daraus über den Rollentausch ein $2^{o(r')}$-Algorithmus für \problem{HittingSet}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $r$:} \begin{itemize} \item Angenommen, \problem{SetCover} wäre in $2^{o(r)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|U'| = r$ wird daraus ein $2^{o(|U'|)}$-Algorithmus für \problem{HittingSet}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(|U|)}$, kein $2^{o(r)}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für Scheduling $2\,|\,\mathrm{prec}, p_i \in \{1,2\}\,|\,C_{\max}$} \textbf{Problem $2\,|\,\mathrm{prec},\ p_i \in \{1,2\}\,|\,C_{\max}$:}\\ \textbf{Gegeben:} Jobs $\mathcal{J}$ (je Job $p_J \in \{1,2\}$) auf $2$ Maschinen, Präzedenzen als DAG $G = (\mathcal{J}, A)$ und $T \in \mathbb{N}_0$.\\ \textbf{Entscheide:} Gibt es einen Schedule (Start- und Maschinenzuweisung je Job), sodass Jobs einer Maschine sich nicht überlappen, $(j,k) \in A$ den Start von $k$ erst nach dem Ende von $j$ erlaubt und der Makespan $\le T$ ist? Reduktion $k\text{-}\problem{Clique} \redp$ Scheduling (zusammenhängender Clique-Graph): Aus $(G = (V,E), k)$ wird \begin{itemize} \item ein Knoten-Job $J_i$ mit $p_i = 1$ je $i \in V$, \item ein Kanten-Job $J_{\{i,j\}}$ mit $p_{\{i,j\}} = 2$ je $\{i,j\} \in E$, \item $3|V| + 2|E|$ Dummy-Jobs mit $p = 1$, also $n = 4|V| + 3|E|$ Jobs, \item Präzedenzen $(J_i, J_{\{i,j\}})$ für alle $i \in V,\ \{i,j\} \in E$ (sowie innerhalb der Dummy-Jobs), \item Makespan $T = 2|V| + 2|E|$. \end{itemize} \begin{enumerate} \item[a)] Geben Sie $n$ und $T$ der Scheduling-Instanz in Abhängigkeit der Clique-Instanz an. \item[b)] Beweisen Sie die ETH-Schranken für das Scheduling-Problem bzgl.\ $n$ und $T$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{Clique} (zusammenhängend) weder in $2^{o(|V|)} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar. \lsg \textbf{a)} Wegen $|V| \le |E| + 1$: \quad $n = 4|V| + 3|E| = O(|E|)$, \quad $T = 2|V| + 2|E| = O(|E|)$. \textbf{b)} \textbf{Bzgl.\ $n$:} \begin{itemize} \item Angenommen, das Scheduling-Problem wäre in $2^{o(\sqrt{n})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $n = O(|E|)$ ist $\sqrt{n} = O(\sqrt{|E|})$. \item Daraus wird ein $2^{o(\sqrt{|E|})}$-Algorithmus für \problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $T$:} \begin{itemize} \item Angenommen, das Scheduling-Problem wäre in $2^{o(\sqrt{T})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $T = O(|E|)$ ist $\sqrt{T} = O(\sqrt{|E|})$. \item Daraus wird ein $2^{o(\sqrt{|E|})}$-Algorithmus für \problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(\sqrt{n})}$, kein $2^{o(\sqrt{T})}$. \hfill$\square$ % ================================================================== \aufg{ETH-Schranke zeigen für ILP-Feasibility} \textbf{Problem \problem{ILP-Feasibility}:}\\ \textbf{Gegeben:} Eine Matrix $A \in \mathbb{Z}^{M \times N}$ und eine rechte Seite $b \in \mathbb{Z}^M$.\\ \textbf{Entscheide:} Gibt es einen Vektor $x \in \mathbb{Z}^N_{\ge 0}$ mit $Ax \le b$? Reduktion $\problem{3-SAT} \redp \problem{ILP-Feasibility}$: Aus Variablen $x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ wird \begin{itemize} \item $N = 2n$ ILP-Variablen, je eine $x_\ell$ pro Literal $\ell$, \item pro Klausel $C_i$ die Ungleichung $-\sum_{\ell \in C_i} x_\ell \le -1$, \item pro Variable $v$ die Ungleichungen $x_v + x_{\bar v} \le 1$ und $-x_v - x_{\bar v} \le -1$. \end{itemize} \begin{enumerate} \item[a)] Geben Sie die Zeilenzahl $M$ und die Spaltenzahl $N$ der ILP-Instanz in Abhängigkeit von $n$ und $m$ an. \item[b)] Beweisen Sie die ETH-Schranken für \problem{ILP-Feasibility} bzgl.\ $M$ und $N$ basierend auf der Reduktion. \end{enumerate} \emph{Hinweis:} Unter der ETH ist \problem{3-SAT} nicht in $2^{o(n)} \cdot |I|^{O(1)}$ lösbar, mit dem Sparsification-Lemma auch nicht in $2^{o(m)} \cdot |I|^{O(1)}$. \lsg \textbf{a)} $M = m + 2n$; wegen $n \le 3m$ also $M = O(m)$. \quad $N = 2n$. \textbf{b)} \textbf{Bzgl.\ $M$:} \begin{itemize} \item Angenommen, \problem{ILP-Feasibility} wäre in $2^{o(M)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $M = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}. \item Widerspruch zur ETH nach dem Sparsification-Lemma. \end{itemize} \textbf{Bzgl.\ $N$:} \begin{itemize} \item Angenommen, \problem{ILP-Feasibility} wäre in $2^{o(N)} \cdot |I|^{O(1)}$ lösbar. \item Wegen $N = 2n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}. \item Direkter Widerspruch zur ETH. \end{itemize} Bounds: kein $2^{o(M)}$, kein $2^{o(N)}$. \hfill$\square$ % ================================================================== \end{document}