\documentclass[11pt]{article}
\input{style.tex}

\title{\textbf{AAK -- Fundament}\\[0.4em]
\large Komplexitätstheorie und Approximation ohne Beweise\\[0.2em]
\normalsize Grundwissen zu Serie 9--13 und Skript Kapitel 6--7}
\author{Klausurvorbereitung \glqq Analyse von Algorithmen und Komplexität\grqq{} (CAU Kiel)}
\date{Sommersemester 2026}

\begin{document}
\maketitle

\noindent\textbf{Wie du dieses Dokument benutzt.}
Dieses PDF baut das Fundament auf: alle Begriffe, Probleme und Resultate des
Klausurstoffs -- bewusst \emph{ohne} Beweise. Zu jedem Satz steht höchstens eine
einzeilige Beweisidee. Arbeite es von vorne nach hinten durch. Wenn alles sitzt,
nimm dir \textbf{Uebung.pdf} vor: Dort lernst du die Beweistechniken und
trainierst die konkreten Klausur-Aufgabentypen.

\medskip
\noindent\textbf{Klausurstoff:} Serien 9--13 und Skript Kapitel 6 (Komplexitätstheorie)
und 7 (Approximative Algorithmen). Mehr kommt nicht dran.

\tableofcontents
\newpage

% ==================================================================
\section{Grundbegriffe: Sprachen und Entscheidungsprobleme}
% ==================================================================

Die Komplexitätstheorie klassifiziert, \emph{wie schwer} Probleme sind.
Ausgangspunkt: Für viele Probleme (z.\,B. Clique) kennt man nur Algorithmen mit
exponentieller Laufzeit. Der naive Clique-Algorithmus (teste alle $k$-elementigen
Teilmengen) braucht im schlimmsten Fall mindestens $2^{|V|/2}$ Schritte
(Lemma~6.2 im Skript). Die Frage \glqq Geht es schneller?\grqq{} führt auf P, NP
und die NP-Vollständigkeit.

\begin{defbox}{Alphabet, Wort, Sprache}
\begin{itemize}
\item Ein \emph{Alphabet} $\Sigma$ ist eine endliche Menge von Symbolen.
\item $\Sigma^*$ ist die Menge aller endlichen Wörter über $\Sigma$; $|x|$ ist die Länge von $x$.
\item Eine Teilmenge $L \subseteq \Sigma^*$ heißt \emph{Sprache}.
\end{itemize}
\end{defbox}

\begin{defbox}{Entscheidungsproblem}
Ein \emph{Entscheidungsproblem} ist ein Tripel $(L, U, \Sigma)$ mit Sprachen
$L \subseteq U \subseteq \Sigma^*$. Ein Algorithmus $A$ \emph{entscheidet} $L$
(bzgl. $U$), wenn für alle $x \in U$ gilt:
$x \in L \Rightarrow A(x) = 1$ und $x \notin L \Rightarrow A(x) = 0$.
Meist ist $U = \Sigma^*$. Die Antwort ist immer \emph{Ja oder Nein}.
\end{defbox}

Jedes konkrete Problem wird als Sprache kodiert. Beispiel Cliquenproblem:
\begin{align*}
\problem{Clique} = \{\, u\#v \mid\; & u \text{ kodiert Adjazenzmatrix von } G,\ v \text{ kodiert } k,\\
& G \text{ hat Clique mit } k \text{ Knoten} \,\}.
\end{align*}
Dabei hat $u$ Länge $O(|V|^2)$ und $v$ Länge $O(\log |V|)$ -- Zahlen werden
\emph{binär} kodiert, sind also exponentiell größer als ihre Kodierungslänge.
Das wird bei SubSet Sum wichtig.

\begin{defbox}{Laufzeit}
$T_A(x)$ ist die Anzahl der Operationen von Algorithmus $A$ auf Eingabe $x$.
Die Worst-Case-Laufzeit für Eingabelänge $n$ ist
$T_A(n) = \max\{\,T_A(x) \mid x \in \Sigma^*,\ |x| = n\,\}$.
\end{defbox}

\begin{merke}
Klausuraufgaben arbeiten fast immer mit \emph{Entscheidungsvarianten}:
Aus einem Optimierungsproblem (\glqq finde minimales Vertex Cover\grqq) wird
eine Ja/Nein-Frage mit Schranke (\glqq gibt es ein Vertex Cover mit $\le k$
Knoten?\grqq).
\end{merke}

% ==================================================================
\section{Die Klassen P und NP}
% ==================================================================

\subsection{P: effizient lösbar}

\begin{defbox}{Klasse P}
$\Pclass$ ist die Menge aller Sprachen, die ein (deterministischer) Algorithmus
in polynomieller Zeit entscheidet:
\[
\Pclass = \{\, L \subseteq \Sigma^* \mid \exists\, \text{Algorithmus } A,\;
T_A(n) = O(n^d) \text{ mit } d = O(1),\; A \text{ entscheidet } L \,\}.
\]
\end{defbox}

Intuition: $\Pclass$ = \glqq effizient lösbar\grqq. Beispiele: Sortieren,
kürzeste Wege, minimale Spannbäume, Matching.

\subsection{NP: effizient überprüfbar}

Für NP gibt es \textbf{zwei gleichwertige Definitionen}. Beide musst du kennen --
die Klausur SS23 hat genau diesen Dreischritt (Zertifikat, Verifizierer, NTM)
abgefragt.

\medskip\noindent\textbf{Weg 1: Verifizierer und Zertifikat.}\par

\begin{defbox}{Verifizierer, Zertifikat}
Ein Algorithmus $A$ auf $\Sigma^* \times \Sigma^*$ heißt \emph{Verifizierer}
für $L$, wenn
\[
L = \{\, x \in \Sigma^* \mid \exists\, c \in \Sigma^* \text{ mit } A(x,c) = 1 \,\}.
\]
Ein Wort $c$ mit $A(x,c) = 1$ heißt \emph{Zertifikat} für $x \in L$.
$A$ ist ein \emph{polynomieller} Verifizierer, wenn es für jedes $x \in L$ ein
Zertifikat $c$ gibt mit $T_A(x,c) = O(|x|^d)$ für eine Konstante $d$.
\end{defbox}

\begin{defbox}{Klasse NP}
$\NP = \{\, L \subseteq \Sigma^* \mid \text{es existiert ein polynomieller
Verifizierer für } L \,\}$.
\end{defbox}

Intuition: Eine Lösung zu \emph{finden} mag schwer sein -- eine vorgelegte
Lösung zu \emph{prüfen} ist leicht. Das Zertifikat ist die vorgelegte Lösung.

\begin{bsp}{Typische Zertifikate}
\begin{center}
\begin{tabular}{lll}
\toprule
Problem & Zertifikat & Prüfung \\
\midrule
$k$-\problem{Clique} & Knotenmenge $C \subseteq V$ & alle Paare in $E$? $|C| \ge k$? \\
\problem{SAT} & Belegung $\psi$ & wertet $\alpha$ zu true aus? \\
\problem{Vertex Cover} & Knotenmenge $C$ & jede Kante überdeckt? $|C| \le k$? \\
\problem{SubSet Sum} & Teilmenge $S$ & $\sum_{j \in S} c_j = K$? \\
\problem{Hamiltonkreis} & Permutation $\pi$ & alle Folgekanten in $E$? \\
\bottomrule
\end{tabular}
\end{center}
Das Zertifikat ist polynomiell lang, die Prüfung läuft in Polynomialzeit.
\end{bsp}

\medskip\noindent\textbf{Weg 2: Nichtdeterminismus.}\par
Ein \emph{nichtdeterministischer Algorithmus} darf in jedem Schritt
\glqq raten\grqq{} (mehrere Rechenwege). Er entscheidet $L$, wenn
(i) jedes $w \in L$ mindestens einen akzeptierenden Rechenweg hat,
(ii) jeder akzeptierende Rechenweg polynomiell lang ist und
(iii) für $w \notin L$ \emph{jeder} Rechenweg ablehnt.
Muster: \emph{Rate die Lösung, prüfe sie deterministisch.}

\begin{defbox}{Nichtdeterministische Turingmaschine (NDTM)}
$M = (Q, \Gamma, q_0, \delta, F)$ mit endlicher Zustandsmenge $Q$,
Arbeitsalphabet $\Gamma \supset \Sigma$, Startzustand $q_0$, Endzuständen
$F \subset Q$ und Übergangsfunktion
\[
\delta:\; Q \times \Gamma \;\longrightarrow\; 2^{\,Q \times \Gamma \times \{-1,0,1\}}.
\]
Zu $(q,a)$ kann es also \emph{mehrere} (oder keine) Übergänge geben.
Eine \emph{Konfiguration} $uqav$ speichert Bandinschrift, Zustand $q$ und
Arbeitsfeld $a$; $C \vdash C'$ bezeichnet den Übergang zur Folgekonfiguration.
Eine Berechnung $C_0, \dots, C_k$ \emph{akzeptiert}, wenn $C_k$ eine
Stopkonfiguration mit Zustand in $F$ ist.
$L \in \NP \iff$ eine NDTM akzeptiert $L$ in nichtdeterministischer
polynomieller Zeit. Ist $|\delta(q,a)| \le 1$ überall, heißt $M$
\emph{deterministisch} (DTM); $L \in \Pclass \iff$ eine DTM entscheidet $L$ in
polynomieller Zeit.
\end{defbox}

\begin{satzbox}{Äquivalenz der NP-Definitionen}
Die Definition über Verifizierer und die über NDTMs beschreiben dieselbe
Klasse $\NP$.\\[0.3em]
\emph{Beweisidee:} Die Folge der Rateschritte einer NDTM \emph{ist} ein
Zertifikat; umgekehrt rät die NDTM das Zertifikat (Phase 1) und simuliert den
Verifizierer (Phase 2).
\end{satzbox}

\begin{satzbox}{$\Pclass \subseteq \NP$}
Jede Sprache in $\Pclass$ liegt auch in $\NP$.\\[0.3em]
\emph{Beweisidee:} Der entscheidende Algorithmus ist ein Verifizierer, der das
Zertifikat einfach ignoriert.
\end{satzbox}

\begin{merke}
Ob $\Pclass = \NP$ gilt, ist \textbf{offen} -- eines der sieben
Millennium-Probleme (Clay Institute, 1~Mio.~Dollar). Alles Weitere
(NP-Vollständigkeit, ETH) ist der Umgang mit dieser Unwissenheit.
\end{merke}

% ==================================================================
\section{Reduktionen, NP-Schwere, NP-Vollständigkeit}
% ==================================================================

\subsection{Polynomielle Reduktionen}

\begin{defbox}{Polynomielle Reduktion $L_1 \redp L_2$}
Seien $L_1 \subseteq \Sigma_1^*$, $L_2 \subseteq \Sigma_2^*$.
Eine Funktion $f: \Sigma_1^* \to \Sigma_2^*$ mit
\[
w \in L_1 \iff f(w) \in L_2 \qquad \forall\, w \in \Sigma_1^*
\]
heißt \emph{Transformation} von $L_1$ auf $L_2$. Sie heißt \emph{polynomiell},
wenn ein Algorithmus $f(w)$ in polynomieller Zeit berechnet (dann ist auch
$|f(w)| \le \poly(|w|)$). Notation: $L_1 \redp L_2$
(\glqq $L_1$ ist polynomiell reduzierbar auf $L_2$\grqq).
\end{defbox}

Intuition: $L_1 \redp L_2$ heißt \emph{\glqq $L_2$ ist mindestens so schwer wie
$L_1$\grqq} -- wer $L_2$ lösen kann, kann damit auch $L_1$ lösen.

\begin{warnung}
\textbf{Die Richtung der Reduktion} ist der häufigste Fehler.
Um zu zeigen, dass ein \emph{neues} Problem $Y$ schwer ist, reduzierst du ein
\emph{bekanntes} schweres Problem $X$ \emph{auf} $Y$: also $X \redp Y$
(\glqq bekannt $\redp$ neu\grqq). Die Reduktion nimmt eine $X$-Instanz und baut
daraus eine $Y$-Instanz -- niemals umgekehrt.
\end{warnung}

\begin{satzbox}{Transitivität}
$L_1 \redp L_2$ und $L_2 \redp L_3$ $\Rightarrow$ $L_1 \redp L_3$.\\[0.3em]
\emph{Beweisidee:} Reduktionen hintereinanderschalten; die Ausgabe der ersten
ist polynomiell groß, also bleibt die Komposition polynomiell.
\end{satzbox}

\subsection{NP-schwer und NP-vollständig}

\begin{defbox}{NP-schwer, NP-vollständig}
\begin{itemize}
\item $L_0$ heißt \emph{NP-schwer} $\iff$ $\forall L \in \NP:\; L \redp L_0$.
\item $L_0$ heißt \emph{NP-vollständig} $\iff$ $L_0 \in \NP$ \textbf{und} $L_0$ ist NP-schwer.
\end{itemize}
\end{defbox}

\begin{merke}
Eselsbrücke: \emph{NP-schwer} = untere Schranke (mindestens so schwer wie alles
in NP). \emph{$\in \NP$} = obere Schranke (nicht schwerer als NP).
\emph{NP-vollständig} = beides. Es gibt NP-schwere Probleme, die nicht in NP
liegen -- z.\,B. das Halteproblem (Abschnitt~\ref{sec:halt}).
\end{merke}

\begin{satzbox}{NP-vollständig und P=NP}
Sei $L_0$ NP-vollständig. Dann gilt: $\Pclass = \NP \iff L_0 \in \Pclass$.\\[0.3em]
\emph{Beweisidee ($\Leftarrow$):} Für beliebiges $L \in \NP$ schalte die
Reduktion $L \redp L_0$ vor den Polynomialzeit-Algorithmus für $L_0$.
\end{satzbox}

Konsequenz: Findet jemand für \emph{ein} NP-vollständiges Problem einen
Polynomialzeit-Algorithmus, kollabiert alles: $\Pclass = \NP$. Solange das
nicht passiert, gilt ein NP-Vollständigkeitsbeweis als starkes Indiz, dass es
keinen effizienten Algorithmus gibt.

\begin{satzbox}{Vererbungskorollar -- das wichtigste Werkzeug}
Ist $L_0$ NP-vollständig, $L_0 \redp L_1$ und $L_1 \in \NP$, so ist $L_1$
NP-vollständig.\\[0.3em]
\emph{Beweisidee:} $L \redp L_0 \redp L_1$ für alle $L \in \NP$ (Transitivität).
\end{satzbox}

Dieses Korollar ist das Standardwerkzeug der Klausur: Statt \glqq alle $L \in
\NP$\grqq{} zu betrachten, reicht \emph{eine} Reduktion von einem bekannten
NP-vollständigen Problem plus der Nachweis $L_1 \in \NP$.

\subsection{Der Startpunkt: Satz von Cook--Levin}

\begin{satzbox}{Cook (1971) / Levin (1973)}
\problem{SAT} ist NP-vollständig.\\[0.3em]
\emph{Beweisidee:} Für beliebiges $L \in \NP$ mit NDTM $M$ wird die Berechnung
von $M$ auf $u$ als KNF-Formel $\alpha_u$ kodiert:
$\alpha_u = \alpha_{\text{Anfang}} \wedge \alpha_{\text{Ende}} \wedge
\alpha_{\text{Eindeutig}} \wedge \alpha_{\text{Übergang}}$ mit Variablen für
\glqq Zustand zur Zeit $t$\grqq, \glqq Arbeitsfeld zur Zeit $t$\grqq,
\glqq Bandinhalt Feld $i$ zur Zeit $t$\grqq. Erfüllende Belegungen entsprechen
genau akzeptierenden Berechnungen; die Formel hat polynomielle Größe
$O(T(n)^3 \log T(n))$.
\end{satzbox}

Ab hier werden alle weiteren NP-Vollständigkeitsbeweise per Reduktionskette aus
SAT aufgebaut (Kapitel~\ref{sec:landkarte}).

% ==================================================================
\section{Problemkatalog}\label{sec:katalog}
% ==================================================================

Alle Probleme des Klausurstoffs im Steckbrief-Format. Präge dir zu jedem ein:
Eingabe, Frage, Status, und \emph{woher} die NP-Vollständigkeit kommt.

\subsection{Logik-Probleme}

\begin{problembox}{SAT}
\textbf{Gegeben:} Boolescher Ausdruck $\alpha = C_1 \wedge \dots \wedge C_m$ in
konjunktiver Normalform (KNF): Klauseln $C_i$ sind Disjunktionen von Literalen
($x_j$ oder $\neg x_j$).\\
\textbf{Entscheide:} Gibt es eine erfüllende Belegung der Variablen?\\
\textbf{Status:} NP-vollständig (Cook--Levin). \emph{Das} Ur-Problem.
\end{problembox}

\begin{problembox}{3-SAT}
\textbf{Gegeben:} KNF-Formel mit \emph{höchstens 3 Literalen pro Klausel}.\\
\textbf{Entscheide:} Erfüllbar?\\
\textbf{Status:} NP-vollständig, via $\problem{SAT} \redp \problem{3-SAT}$
(lange Klauseln mit Hilfsvariablen aufspalten).
Startpunkt fast aller ETH-Reduktionen. Variante \problem{3-SAT$'$}
(\emph{genau} 3 Literale) ist ebenfalls NP-vollständig.
\end{problembox}

\begin{problembox}{MAX-3-SAT (Optimierungsproblem)}
\textbf{Gegeben:} KNF-Formel, jede Klausel mit 3 Literalen.\\
\textbf{Gesucht:} Belegung $\beta$, die die Anzahl $v(\beta)$ erfüllter
Klauseln maximiert.\\
\textbf{Status:} Optimierungsvariante von 3-SAT; in der Klausur als
\emph{Approximationsaufgabe} (Güte-2-Algorithmus, siehe
Abschnitt~\ref{sec:approx-max3sat}).
\end{problembox}

\subsection{Graphprobleme}

\begin{problembox}{$k$-Clique}
\textbf{Gegeben:} Ungerichteter Graph $G = (V,E)$, Zahl $k \ge 1$.
Eine \emph{Clique} ist $C \subseteq V$ mit $\{u,v\} \in E$ für alle $u \ne v$
aus $C$.\\
\textbf{Entscheide:} Existiert eine Clique mit $|C| \ge k$?\\
\textbf{Status:} NP-vollständig, via $\problem{SAT} \redp \problem{$k$-Clique}$
(Vorlesungsbeweis -- auswendig können!).
\end{problembox}

\begin{bsp}{Clique}
\setlength{\unitlength}{0.9cm}
\begin{center}
\begin{picture}(3.6,2.4)(-0.3,-0.2)
\put(0,1){\circle*{0.12}}\put(-0.3,1){\small $1$}
\put(1,2){\circle*{0.12}}\put(1,2.15){\small $2$}
\put(2,1){\circle*{0.12}}\put(2.1,1.15){\small $3$}
\put(1.5,0){\circle*{0.12}}\put(1.4,-0.35){\small $4$}
\put(3,0){\circle*{0.12}}\put(3.1,-0.2){\small $5$}
\put(0,1){\line(1,1){1}}      % 1-2
\put(0,1){\line(1,0){2}}      % 1-3
\put(1,2){\line(1,-1){1}}     % 2-3
\put(2,1){\line(-1,-2){0.5}}  % 3-4
\put(2,1){\line(1,-1){1}}     % 3-5
\end{picture}
\end{center}
$C = \{1,2,3\}$ ist eine Clique der Größe 3; $\{2,3,4\}$ nicht (Kante
$\{2,4\}$ fehlt).
\end{bsp}

\begin{problembox}{Independent Set (IS)}
\textbf{Gegeben:} $G = (V,E)$, Zahl $k$. Ein \emph{Independent Set} ist
$I \subseteq V$ ohne Kante zwischen zwei Knoten aus $I$.\\
\textbf{Entscheide:} Gibt es ein Independent Set mit $|I| \ge k$?\\
\textbf{Status:} NP-vollständig -- $C$ ist Clique in $G$ $\iff$ $C$ ist
Independent Set im Komplementgraphen $\bar{G}$.
\end{problembox}

\begin{problembox}{Vertex Cover (VC)}
\textbf{Gegeben:} $G = (V,E)$, Zahl $k$. Ein \emph{Vertex Cover} ist
$C \subseteq V$, sodass jede Kante mindestens einen Endpunkt in $C$ hat.\\
\textbf{Entscheide:} Gibt es ein Vertex Cover mit $|C| \le k$?\\
\textbf{Status:} NP-vollständig, via $\problem{Clique} \redp \problem{VC}$.
\end{problembox}

\begin{merke}
\textbf{Dualitätsdreieck} (Kern vieler Aufgaben): In $G$ mit $n$ Knoten gilt
\begin{align*}
C \text{ ist Clique der Größe } k \text{ in } G
&\iff C \text{ ist IS der Größe } k \text{ in } \bar{G}\\
&\iff V \setminus C \text{ ist VC der Größe } n-k \text{ in } \bar{G}.
\end{align*}
Merksatz: \emph{Vertex Cover = Komplement eines Independent Set}
(in demselben Graphen), \emph{Clique = Independent Set im Komplementgraphen}.
\end{merke}

\begin{problembox}{$k$-Color (Färbungsproblem)}
\textbf{Gegeben:} $G = (V,E)$, Zahl $k$. Eine \emph{$k$-Färbung} ist
$f: V \to \{1,\dots,k\}$ mit $f(u) \ne f(v)$ für alle $\{u,v\} \in E$.\\
\textbf{Entscheide:} Ist $G$ $k$-färbbar?\\
\textbf{Status:} NP-vollständig, via $\problem{3-SAT} \redp \problem{$k$-Color}$
(Konstruktion mit $n+1$ Farben, Knoten $x_i, \bar{x}_i, v_i$, Klauselknoten
$F_j$ und Zentrum $z$). Auch \problem{3-Color} ist NP-vollständig.
\end{problembox}

\begin{problembox}{Hamiltonkreis (HK) und Hamiltonpfad}
\textbf{Gegeben:} $G = (V,E)$ ungerichtet (Aussage gilt auch gerichtet).\\
\textbf{Entscheide:} Gibt es einen Kreis, der jeden Knoten \emph{genau einmal}
besucht (formal: Permutation $\pi$ mit $\{v_{\pi(i)}, v_{\pi(i+1)}\} \in E$
zyklisch)?\\
\textbf{Status:} NP-vollständig, via $\problem{3-SAT}' \redp \problem{HK}$
(Gadget-Konstruktion mit A-/B-Komponenten; nur Beweisskizze im Skript).
\problem{Hamiltonpfad} (Pfad statt Kreis) ist ebenfalls NP-vollständig;
Klausur SS23 verlangte die Reduktionen zwischen beiden in \emph{beide}
Richtungen.
\end{problembox}

\begin{problembox}{TSP (Traveling Salesman, Entscheidungsvariante)}
\textbf{Gegeben:} Knoten $\{1,\dots,n\}$, Distanzen $d(i,j)$, Schranke $L$.\\
\textbf{Entscheide:} Gibt es eine Rundreise (jeder Knoten genau einmal) mit
Länge $\le L$?\\
\textbf{Status:} NP-vollständig, via $\problem{HK} \redp \problem{TSP}$
(Kanten $\mapsto$ Distanz 1, Nicht-Kanten $\mapsto |V|+1$, $L = |V|$).
Bleibt NP-vollständig im metrischen Fall ($\Delta$-Ungleichung).
Als Optimierungsproblem zentral in Kapitel~\ref{sec:approx}.
\end{problembox}

\begin{problembox}{Feedback Vertex Set (FVS)}
\textbf{Gegeben:} \emph{Gerichteter} Graph $G = (V,E)$, Zahl $k$.\\
\textbf{Entscheide:} Gibt es $X \subseteq V$ mit $|X| \le k$, sodass
$G \setminus X$ kreisfrei ist?\\
\textbf{Status:} NP-vollständig, via $\problem{VC} \redp \problem{FVS}$
(Serie 9/10: jede ungerichtete Kante wird zu zwei antiparallelen Bögen).
\end{problembox}

\begin{problembox}{$\Delta$-Cover (Dreiecksüberdeckung)}
\textbf{Gegeben:} $G = (V,E)$ ungerichtet, Zahl $k$.\\
\textbf{Entscheide:} Gibt es $C_\Delta \subseteq V$, $|C_\Delta| \le k$, das
\emph{jede 3-Clique} (Dreieck) von $G$ trifft?\\
\textbf{Status:} NP-vollständig, via $\problem{VC} \redp \Delta\problem{-Cover}$
(Serie 11: jede Kante zu einem Dreieck aufblasen).
\end{problembox}

\begin{problembox}{Dominating Set}
\textbf{Gegeben:} $G = (V,E)$, Zahl $k$.\\
\textbf{Entscheide:} Gibt es $D \subseteq V$, $|D| \le k$, sodass jeder Knoten
in $D$ liegt oder einen Nachbarn in $D$ hat?\\
\textbf{Status:} NP-vollständig. In Klausuren als NP-Zugehörigkeits- und
ETH-Beispiel (Reduktion von 3-SAT vorgegeben).
\end{problembox}

\begin{problembox}{Longest Path}
\textbf{Gegeben:} $G = (V,E)$, Zahl $k$.\\
\textbf{Entscheide:} Gibt es einen einfachen Pfad der Länge $\ge k$?\\
\textbf{Status:} NP-vollständig (verallgemeinert Hamiltonpfad). In der Klausur
SS23 als NP-Zugehörigkeits-Aufgabe (Zertifikat/Verifizierer/NTM).
\end{problembox}

\subsection{Mengen- und Zahlprobleme}

\begin{problembox}{3-dimensionales Matching (3-DM)}
\textbf{Gegeben:} Mengen $U, V, W$ mit $|U| = |V| = |W|$ und
$T \subseteq V \times W \times U$.\\
\textbf{Entscheide:} Gibt es $M \subseteq T$ mit $|M| = |U|$, sodass keine zwei
Tripel in einer Komponente übereinstimmen?\\
\textbf{Status:} NP-vollständig, via $\problem{SAT} \redp \problem{3-DM}$
(Gadgets: $a/b$-Knoten für Variablensetzung, $v/w$ für Klauselwahl, $c/d$ als
Garbage Collection).
\end{problembox}

\begin{problembox}{3-Exact Cover (3-EC)}
\textbf{Gegeben:} Familie $F = \{S_1, \dots, S_n\}$ von 3-elementigen
Teilmengen einer Menge $U$ mit $|U| = 3m$.\\
\textbf{Entscheide:} Gibt es $m$ Mengen aus $F$, die $U$ exakt überdecken
(disjunkt, Vereinigung $= U$)?\\
\textbf{Status:} NP-vollständig -- jede 3-DM-Instanz \emph{ist} eine
3-EC-Instanz (Uminterpretation).
\end{problembox}

\begin{problembox}{SubSet Sum}
\textbf{Gegeben:} Ganze Zahlen $c_1, \dots, c_n$ und Zielwert $K$.\\
\textbf{Entscheide:} Gibt es $S \subseteq \{1,\dots,n\}$ mit
$\sum_{j \in S} c_j = K$?\\
\textbf{Status:} NP-vollständig, via $\problem{3-EC} \redp \problem{SubSet Sum}$
(Mengen als Bitvektoren zur Basis $n+1$).
\textbf{Klausur-Spitzenreiter:} In jeder Altklausur taucht eine
SubSet-Sum-Variante auf.
\end{problembox}

\begin{problembox}{Partition}
\textbf{Gegeben:} Ganze Zahlen $c_1, \dots, c_n$.\\
\textbf{Entscheide:} Gibt es $S$ mit
$\sum_{j \in S} c_j = \tfrac{1}{2}\sum_{j=1}^n c_j$?\\
\textbf{Status:} NP-vollständig, via $\problem{SubSet Sum} \redp
\problem{Partition}$ (zwei Zusatzzahlen $N - K$ und $K + 1$).
\end{problembox}

\begin{problembox}{Rucksackproblem (Knapsack, Entscheidungsvariante)}
\textbf{Gegeben:} $n$ Gegenstände mit Größen $c_j$ und Profiten $p_j$,
Kapazität $K$, Zielprofit $P$.\\
\textbf{Entscheide:} Gibt es $S$ mit $\sum_{j \in S} c_j \le K$ und
$\sum_{j \in S} p_j \ge P$?\\
\textbf{Status:} NP-vollständig -- SubSet Sum ist der Spezialfall $c_j = p_j$,
$P = K$. Als Optimierungsproblem zentral in Kapitel~\ref{sec:approx}
(Greedy, FPTAS).
\end{problembox}

\begin{problembox}{Hitting Set}
\textbf{Gegeben:} Universum $U$, Teilmengen $F_1, \dots, F_r \subseteq U$,
Zahl $k$.\\
\textbf{Entscheide:} Gibt es $S \subseteq U$, $|S| \le k$, mit
$S \cap F_i \ne \emptyset$ für alle $i$ (\glqq $S$ trifft jede Menge\grqq)?\\
\textbf{Status:} NP-vollständig; via $\problem{3-SAT} \redp \problem{Hitting
Set}$ (Serie 13). Standard-Beispiel für ETH-Lower-Bounds.
\end{problembox}

\begin{problembox}{Set Cover}
\textbf{Gegeben:} Universum $U$, Mengen $S_1, \dots, S_r \subseteq U$, Zahl $k$.\\
\textbf{Entscheide:} Gibt es $\le k$ Mengen, deren Vereinigung $U$ ist?\\
\textbf{Status:} NP-vollständig; dual zu Hitting Set (Klausur SS23:
$\problem{Set Cover} \redp \problem{Hitting Set}$ für ETH-Schranken).
\end{problembox}

\subsection{Scheduling}

\begin{problembox}{$P\,\|\,C_{\max}$ (Scheduling auf identischen Maschinen)}
\textbf{Gegeben:} $n$ Jobs mit Laufzeiten $p_1, \dots, p_n$, $m$ identische
Maschinen.\\
\textbf{Gesucht:} Partition der Jobs in $B_1, \dots, B_m$ mit minimalem
\emph{Makespan} $\Cmax = \max_i \sum_{J_j \in B_i} p_j$.\\
\textbf{Status:} NP-vollständig schon für $m = 2$ (Reduktion von
\problem{Partition}). Zentrale Approximationsalgorithmen: List Scheduling,
LPT (Kapitel~\ref{sec:approx}).
\end{problembox}

% ==================================================================
\section{Die Reduktionslandkarte}\label{sec:landkarte}
% ==================================================================

Alle NP-Vollständigkeitsbeweise des Stoffs hängen an dieser Kette
(Pfeil $=$ \glqq wird reduziert auf\grqq):

\begin{center}
\begin{tabular}{ccccc}
 & & $\boxed{\textbf{\problem{SAT}}}$ \; {\footnotesize (Cook--Levin)} & & \\[0.5em]
$\swarrow$ & & $\downarrow$ & & $\searrow$ \\[0.5em]
$\problem{3-SAT}$ & & $\problem{$k$-Clique}$ & & $\problem{3-DM}$ \\[0.5em]
$\downarrow$ & & $\downarrow$ & & $\downarrow$ \\[0.5em]
$\problem{$k$-Color}$ & & $\problem{IS}$, $\problem{VC}$ & & $\problem{3-EC}$ \\[0.5em]
 & & $\downarrow$ & & $\downarrow$ \\[0.5em]
$\problem{3-SAT}' \to \problem{HK} \to \problem{TSP}$ & & $\problem{FVS}$, $\Delta$\problem{-Cover} & & $\problem{SubSet Sum}$ \\[0.5em]
 & & & & $\downarrow$ \\[0.5em]
 & & & & $\problem{Partition} \to P\,\|\,\Cmax$;\; $\problem{Knapsack}$ \\
\end{tabular}
\end{center}

\medskip
Die Konstruktionsideen im Überblick (Details und Beweise in Uebung.pdf):

\begin{center}
\footnotesize
\begin{tabular}{lll}
\toprule
Reduktion & Kernidee der Konstruktion & Quelle \\
\midrule
$\problem{SAT} \redp \problem{3-SAT}$ & lange Klauseln per Hilfsvariablen-Kette aufspalten & Skript 6.25 \\
$\problem{SAT} \redp \problem{$k$-Clique}$ & Knoten $[i,j]$ pro Literal; Kanten = konsistent, andere Klausel & Skript 6.26 \\
$\problem{3-SAT} \redp \problem{$k$-Color}$ & $n{+}1$ Farben; Clique $\{v_1,\dots,v_n,z\}$ erzwingt Setzung & Skript 6.28 \\
$\problem{Clique} \redp \problem{VC}$ & Komplementgraph; $C$ Clique $\iff V \setminus C$ VC, $k' = n-k$ & Präsenz 10 \\
$\problem{VC} \redp \problem{FVS}$ & Kante $\to$ zwei antiparallele Bögen (2-Kreise) & Serie 10 \\
$\problem{VC} \redp \Delta\problem{-Cover}$ & Kante $\{u,v\} \to$ Dreieck $\{v_e, u, v\}$ & Serie 11 \\
$\problem{SAT} \redp \problem{3-DM}$ & Variablen-Rad, Klausel-Tripel, Garbage Collection & Skript 6.30 \\
$\problem{3-DM} \redp \problem{3-EC}$ & Uminterpretation (Tripel = 3er-Mengen) & Skript 6.31 \\
$\problem{3-EC} \redp \problem{SubSet Sum}$ & Mengen als Bitvektoren zur Basis $n{+}1$; kein Übertrag & Skript 6.32 \\
$\problem{SubSet Sum} \redp \problem{Partition}$ & Zusatzzahlen $N{-}K$ und $K{+}1$ & Skript 6.33 \\
$\problem{3-SAT}' \redp \problem{HK}$ & A-Komponenten (XOR), B-Komponenten (Klauseln) & Skript 6.42 \\
$\problem{HK} \redp \problem{TSP}$ & Kanten Distanz 1, Nicht-Kanten $|V|{+}1$, $L = |V|$ & Skript 7.2 \\
$\problem{Partition} \redp P2\,\|\,\Cmax$ & Zahlen = Jobs; Makespan $\tfrac12\sum c_j$? & Skript 7.23 \\
$\problem{3-SAT} \redp \problem{SubSet Sum}$ (streng) & Ziffern zur Basis 10; $|A| = O(m)$ -- für ETH & Skript 6.40 \\
\bottomrule
\end{tabular}
\end{center}

% ==================================================================
\section{ETH: Exponentialzeit-Hypothese und untere Schranken}\label{sec:eth}
% ==================================================================

NP-Vollständigkeit sagt nur \glqq vermutlich nicht polynomiell\grqq. Die ETH
ist eine \emph{stärkere} Annahme, mit der man konkrete exponentielle
\emph{untere Laufzeitschranken} herleitet. In \textbf{jeder} Altklausur ist die
letzte Aufgabe eine ETH-Aufgabe.

\begin{defbox}{Klein-o-Notation}
$f(x) = o(g(x)) \iff$ für \emph{jedes} $c > 0$ gilt ab einem $x_0$:
$|f(x)| \le c \cdot |g(x)|$; äquivalent $f(x)/g(x) \to 0$.
Beispiele: $\sqrt{n} = o(n)$, $n/\log n = o(n)$, aber $\delta n \ne o(n)$ für
festes $\delta > 0$. Ein \glqq $2^{o(n)}$-Algorithmus\grqq{} ist also einer,
der \emph{subexponentiell} in $n$ läuft.
\end{defbox}

\begin{satzbox}{Exponentialzeit-Hypothese (ETH; Impagliazzo, Paturi, Zane 2001)}
Es existiert ein $\delta > 0$, sodass \problem{3-SAT} mit $n$ Variablen und $m$
Klauseln \emph{nicht} in Zeit $2^{\delta n} (n+m)^{O(1)}$ gelöst werden kann.\\[0.3em]
Äquivalent formuliert: Es gibt keinen $2^{o(n)} \cdot \poly$-Algorithmus für
\problem{3-SAT}. (Unbewiesene Annahme; alle bekannten 3-SAT-Algorithmen
brauchen $c^n$, derzeit bestes $c \approx 1{,}307$.)
\end{satzbox}

\begin{satzbox}{Sparsification-Lemma}
Unter der ETH existiert $\delta' > 0$, sodass \problem{3-SAT} nicht in Zeit
$2^{\delta' m} (n+m)^{O(1)}$ lösbar ist -- also auch kein
$2^{o(m)}$-Algorithmus (Schranke in der \emph{Klauselzahl} $m$).
\end{satzbox}

\begin{merke}
Warum braucht man das Lemma? Die ETH spricht über $n$ (Variablen). Reduktionen
erzeugen Instanzgrößen aber oft abhängig von $m$ (Klauseln). Es gilt zwar
$n \le 3m$ (jede Variable komme vor), aber $m$ kann bis $O(n^3)$ groß sein --
eine $2^{o(m)}$-Schranke folgt daher \emph{nicht} direkt aus der ETH. Das
Sparsification-Lemma schließt genau diese Lücke.
In Klausurlösungen: Immer wenn dein Parameter an $m$ hängt, das
Sparsification-Lemma zitieren.
\end{merke}

\begin{satzbox}{ETH-Konsequenzen (Skript 6.37--6.40)}
Unter Annahme der ETH gibt es keinen $2^{o(n)} \cdot \poly$-Algorithmus für:
\problem{3-Color} ($n = $ Knotenzahl; via Reduktion mit $O(n+m)$ Knoten),
\problem{Clique}, \problem{Vertex Cover}, \problem{Independent Set},
sowie \problem{SubSet Sum} und \problem{Partition} ($n = $ Anzahl Zahlen;
via strenger Reduktion mit $|A| = O(m)$ Items).
\end{satzbox}

Das Beweisschema (Kontraposition) lernst du in Uebung.pdf, Kapitel 5:
\emph{Gäbe es einen $2^{o(\text{Parameter})}$-Algorithmus für das Zielproblem,
ergäbe die Reduktion einen $2^{o(m)}$-Algorithmus für 3-SAT -- Widerspruch zum
Sparsification-Lemma.} Entscheidend ist, die Parameter der konstruierten
Instanz (Knoten, Kanten, $k$, \dots) durch $n$ und $m$ abzuschätzen.

% ==================================================================
\section{Approximative Algorithmen}\label{sec:approx}
% ==================================================================

Wenn exakte Lösungen (vermutlich) exponentielle Zeit brauchen, berechnet man in
Polynomialzeit \emph{beweisbar gute Näherungen}.

\subsection{Gütebegriff und Approximationsschemata}

\begin{defbox}{Multiplikative (Worst-Case-)Güte}
Sei $A$ ein Algorithmus für ein Optimierungsproblem, $\OPT(I)$ der optimale
Wert zu Instanz $I$. $A$ hat Güte $\alpha$, wenn für \emph{alle} Instanzen $I$:
\begin{itemize}
\item Minimierungsproblem: $A(I) \le \alpha \cdot \OPT(I)$ \quad (z.\,B. TSP, VC, $\Cmax$),
\item Maximierungsproblem: $A(I) \ge \tfrac{1}{\alpha} \cdot \OPT(I)$ \quad (z.\,B. Knapsack, MAX-3-SAT).
\end{itemize}
Die Güte ist \emph{scharf}, wenn es Instanzen gibt, die den Faktor (beliebig
genau) erreichen.
\end{defbox}

\begin{defbox}{PTAS, EPTAS, FPTAS}
Eine Familie $(A_\varepsilon)$ von Algorithmen mit Güte $1 + \varepsilon$ für
jedes $\varepsilon > 0$ heißt
\begin{itemize}
\item \emph{PTAS} (polynomielles Approximationsschema): Laufzeit polynomiell in
$n$ für jedes feste $\varepsilon$ (z.\,B. $O(n^{1/\varepsilon})$),
\item \emph{EPTAS}: Laufzeit $f(1/\varepsilon) \cdot \poly(n)$
(z.\,B. $2^{O(1/\varepsilon \log^2(1/\varepsilon))} + O(n)$ für $P\,\|\,\Cmax$),
\item \emph{FPTAS}: Laufzeit polynomiell in $n$ \emph{und} $1/\varepsilon$
(z.\,B. $O(n^3/\varepsilon)$ für Knapsack). Stärkste Form.
\end{itemize}
\emph{Pseudo-polynomiell} heißt eine Laufzeit, die polynomiell in den
\emph{Zahlenwerten} der Eingabe ist (z.\,B. $O(n^2 p_{\max})$ beim
Knapsack-DP) -- aber exponentiell in der Kodierungslänge.
\end{defbox}

\subsection{TSP: $\Delta$TSP$_1$ und Christofides}

\begin{satzbox}{Allgemeines TSP ist nicht approximierbar}
Für das allgemeine TSP gibt es \emph{keinen} Approximationsalgorithmus mit
beschränkter Güte $\alpha$, außer $\Pclass = \NP$.\\[0.3em]
\emph{Beweisidee:} Reduktion von \problem{HK}: Nicht-Kanten bekommen Distanz
$\infty$ (bzw. $\alpha |V| + 1$); ein $\alpha$-Approximationsalgorithmus könnte
dann Hamiltonkreise erkennen. (Klausuraufgabe SS23!)
\end{satzbox}

Deshalb: \emph{metrisches TSP} ($\Delta$-TSP) mit symmetrischen Distanzen und
Dreiecksungleichung $d(i,j) \le d(i,k) + d(k,j)$. Bleibt NP-vollständig, ist
aber approximierbar.

\begin{rezept}{Algorithmus $\Delta$TSP$_1$ (MST-Verdopplung) -- Güte 2}
\begin{enumerate}
\item Berechne minimalen Spannbaum $T$ von $K_n$ mit Distanzen $d$.
\item Verdopple alle Kanten von $T$ $\to$ Multigraph $G$ (alle Grade gerade).
\item Bestimme Eulerkreis $K$ in $G$.
\item Kürze $K$ zu Rundreise $R$ ab (bereits besuchte Knoten überspringen).
\end{enumerate}
Güte-Argument (nur Idee): $w(T) \le \OPT$ (Tour minus Kante = Spannbaum),
$d(K) = 2w(T)$, Abkürzen verlängert wegen $\Delta$-Ungleichung nicht.
Also $d(R) \le 2\,\OPT$. Schranke ist asymptotisch scharf (Stern-Beispiel:
$\OPT = n$, Ausgabe $2n - 2$).
\end{rezept}

\begin{defbox}{Eulerkreis}
Ein \emph{Eulerkreis} in einem Multigraphen besucht jede \emph{Kante} genau
einmal. Existenzkriterium: $G$ zusammenhängend und \emph{jeder Knoten hat
geraden Grad} (Königsberger Brückenproblem).
\end{defbox}

\begin{bsp}{$\Delta$TSP$_1$ durchgerechnet (Skript-Beispiel 7.7)}
$V = \{A,B,C,D,E\}$; optimale Tour $[C,B,D,E,A,C]$ mit Länge 8.
Der MST hat Gewicht 6 (Kanten $CB$, $BA$ je 1, $CD$, $AE$ je 2).
Verdopplung: Multigraph mit Gewicht 12.
Eulerkreis $K = [C,A,E,A,C,B,C,D,C]$, Abkürzen liefert
$R = [C,A,E,B,D,C]$ mit Länge 10 $\le 2 \cdot 8$.
\end{bsp}

\begin{rezept}{Algorithmus $\Delta$TSP$_2$ (Christofides) -- Güte 1{,}5}
\begin{enumerate}
\item Berechne minimalen Spannbaum $T$.
\item $X :=$ Knoten mit \emph{ungeradem} Grad in $T$ ($|X|$ ist gerade).
\item Berechne ein perfektes Matching $K$ mit minimalem Gewicht auf $X$
(geht in $O(|V|^3)$, Lawler 1976).
\item $G := T + K$ (alle Grade gerade), Eulerkreis, abkürzen.
\end{enumerate}
Güte-Argument (nur Idee): Die optimale Tour zerfällt auf $X$ in zwei Matchings
$M_1, M_2$ mit $d(M_1) + d(M_2) \le \OPT$; also $d(K) \le \OPT/2$ und
$d(R) \le w(T) + d(K) \le 1{,}5\,\OPT$. Auch diese Schranke ist asymptotisch
scharf (Leiter-Beispiel, Präsenzserie 12: Rate $\to 3/2 - 1/n$).
\end{rezept}

\begin{warnung}
Klausur-Klassiker: \emph{Warum braucht Christofides die
$\Delta$-Ungleichung?} Beim Abkürzen des Eulerkreises darf der Weg nicht länger
werden -- das garantiert nur die Dreiecksungleichung. Und: Das Matching wird
auf den \emph{ungerad-gradigen Knoten des MST} gebildet, nicht auf allen.
\end{warnung}

\subsection{Knapsack: Greedy, MGA, FPTAS}

\begin{rezept}{Greedy GA -- Güte unbeschränkt!}
Sortiere nach Profitdichte $p_i/w_i$ absteigend; nimm jeden Gegenstand, der
noch passt. Laufzeit $O(n \log n)$.\\[0.3em]
\textbf{Aber:} Instanz $(w_0,p_0) = (1,1)$, $(w_1,p_1) = (B, B-1)$:
GA nimmt Gegenstand 0 (Dichte 1), Gewinn 1; optimal ist $B-1$.
Güte $\ge B - 1$, also \emph{keine} konstante Güte.
\end{rezept}

\begin{rezept}{Modified Greedy MGA -- Güte 2}
Berechne $S_1$ mit GA \emph{und} $S_2 = \{$Gegenstand mit maximalem
Einzelprofit$\}$; gib die bessere Lösung aus.\\[0.3em]
Güte-Argument (nur Idee): Die fraktionale Relaxierung packt nach Dichte und
schneidet beim \emph{Split-Item} $k{+}1$ ab:
$\OPT \le \OPT_f \le \mathrm{GA}(I) + p_{k+1} \le \mathrm{GA}(I) + p_{\max}
\le 2 \cdot \mathrm{MGA}(I)$.
\end{rezept}

\begin{satzbox}{Sahni-Algorithmus $A_k$ ($k$-Enumeration)}
Probiere alle Teilmengen $S$ mit $|S| \le k$ als Vorplatzierung, fülle mit GA
auf, nimm das Beste. Güte $\le 1 + 1/k$, Laufzeit $O(n^{k+1})$ -- ein PTAS.
\end{satzbox}

\begin{satzbox}{FPTAS für Knapsack (Profit-Skalierung)}
Skaliere Profite $p_i' = \lfloor p_i / K \rfloor$ mit
$K = \frac{\varepsilon\, p_{\max}}{(1+\varepsilon)\,n}$, löse mit dem
pseudopolynomiellen DP ($O(n^2 p'_{\max})$), gib dessen Lösung aus.
Laufzeit $O(n^3/\varepsilon)$, Güte $1 + \varepsilon$.\\[0.3em]
\emph{Idee:} Durch Abrunden verliert jede Lösung höchstens $K$ pro Item, also
$\le Kn$ gesamt; wegen $\OPT \ge p_{\max}$ ist der relative Fehler $\le \varepsilon$.
\end{satzbox}

\subsection{Scheduling: List Scheduling und LPT}

\begin{rezept}{List Scheduling -- Güte $2 - \frac{1}{m}$}
Gehe die Jobs in Listenreihenfolge durch; weise jeden Job der Maschine mit
aktuell \emph{kleinster Last} zu.\\[0.3em]
Güte-Argument (nur Idee): Sei $J_k$ der letzte Job auf der vollsten Maschine.
Bis zu seinem Start waren alle Maschinen beschäftigt:
$\mathrm{LS}(I) - p_k \le \frac{1}{m}\sum_i p_i \le \OPT$ und $p_k \le \OPT$
ergeben $\mathrm{LS}(I) \le (2 - \frac{1}{m})\OPT$. Die Schranke wird von
konkreten Instanzen erreicht (Klausuraufgabe: solche Instanzen konstruieren!).
\end{rezept}

\begin{rezept}{LPT Scheduling -- Güte $\frac{4}{3} - \frac{1}{3m}$}
\emph{Longest Processing Time first}: Sortiere die Jobs absteigend
($p_1 \ge p_2 \ge \dots$), dann List Scheduling.\\[0.3em]
Beweis über minimales Gegenbeispiel: Dort wäre $p_n > \OPT/3$, also höchstens
2 Jobs pro Maschine im Optimum; per Austausch-Transformationen wird das
Optimum in einen LPT-Schedule überführt -- Widerspruch. Auch $4/3 - 1/(3m)$
wird asymptotisch erreicht.
\end{rezept}

\begin{bsp}{List Scheduling vs. LPT, $m = 2$}
Jobs mit Zeiten $(1, 1, 2)$ in Listenreihenfolge:
List Scheduling legt die beiden Einsen auf $M_1$ und $M_2$, die 2 dann auf
$M_1$ $\Rightarrow \Cmax = 3$. Optimal ist $\{2\}/\{1,1\}$ mit $\OPT = 2$.
Die Rate ist $3/2 = 2 - \frac{1}{m}$ -- die Schranke wird exakt erreicht.
LPT sortiert zuerst: $(2,1,1)$ ergibt $\Cmax = 2 = \OPT$.
\end{bsp}

\begin{satzbox}{EPTAS für $P\,\|\,\Cmax$}
Für jedes $\varepsilon > 0$ gibt es $A_\varepsilon$ mit
$A_\varepsilon(I) \le (1+\varepsilon)\OPT(I)$ und Laufzeit
$2^{O(1/\varepsilon \cdot \log^2 (1/\varepsilon))} + O(n)$.
\end{satzbox}

\subsection{MAX-3-SAT: Güte 2}\label{sec:approx-max3sat}

\begin{rezept}{Komplementäre Belegungen -- Güte 2}
Werte die Formel unter $\beta_0$ (alle Variablen false) und $\beta_1$ (alle
true) aus; gib die bessere Belegung zurück.\\[0.3em]
Warum das funktioniert: Jede Klausel enthält ein positives oder ein negatives
Literal, wird also von $\beta_0$ \emph{oder} $\beta_1$ erfüllt. Daher
$v(\beta_0) + v(\beta_1) \ge m$, also $\max \ge m/2 \ge \OPT/2$.
(Beweis + scharfe Instanz: Uebung.pdf -- war Klausuraufgabe SoSe 23.)
\end{rezept}

% ==================================================================
\section{Halteproblem und Unentscheidbarkeit}\label{sec:halt}
% ==================================================================

\begin{problembox}{HALT$_{\text{TM}}$ (Halteproblem)}
\textbf{Gegeben:} Kodierung $\langle M, w \rangle$ einer DTM $M$ und eines
Wortes $w$.\\
\textbf{Entscheide:} Hält $M$ auf $w$ (erreicht eine Stopkonfiguration)?\\
\textbf{Status:} \emph{Unentscheidbar} -- kein Algorithmus löst es, egal mit
welcher Laufzeit. Trotzdem \textbf{NP-schwer} (Serie 11): via
$\problem{SAT} \redp \problem{HALT}_{\text{TM}}$; konstruiere $M_\varphi$, die
alle Belegungen durchprobiert und genau dann hält, wenn eine erfüllende
existiert.
\end{problembox}

\begin{merke}
HALT$_{\text{TM}}$ ist NP-schwer, aber \emph{nicht} NP-vollständig -- es liegt
nicht in NP (nicht einmal entscheidbar). Wichtig ist die Pointe der Reduktion:
$M_\varphi$ läuft womöglich ewig, aber die \emph{Konstruktion} von
$\langle M_\varphi, \varepsilon \rangle$ aus $\varphi$ ist polynomiell -- nur
darauf kommt es an. (In den Altklausuren kam das Thema nie dran; Serienstoff
ist es trotzdem.)
\end{merke}

% ==================================================================
\section{Wahr oder falsch? Die Logik-Merkkiste}
% ==================================================================

Aussagen aus den Präsenzserien 10/11 -- ideale Selbstkontrolle:

\begin{center}
\small
\begin{tabular}{p{7.9cm}cp{4.4cm}}
\toprule
Aussage & W/F & Begründung \\
\midrule
Jedes Problem, das eine NDTM in Polyzeit löst, löst auch eine DTM in Polyzeit. &
F$^*$ & Das wäre $\Pclass = \NP$; gilt nur, falls $\Pclass = \NP$. \\
\addlinespace
$A$ NP-schwer $\Rightarrow A \in \Pclass$ ausgeschlossen? / $A$ NP-schwer
$\Rightarrow A \in \NP$? & F & NP-schwer sagt nichts über Zugehörigkeit zu NP
(Bsp. Halteproblem). $A \in \Pclass$ würde $\Pclass = \NP$ implizieren. \\
\addlinespace
$L \in \NP$ und $L \redp \problem{3-SAT}$ $\Rightarrow$ $L$ NP-vollständig. &
F & Gegenbeispiel $L = \emptyset$ bzw. jedes einfache $L$: reduzierbar
\emph{auf} 3-SAT heißt nicht schwer. \\
\addlinespace
$L \redp \problem{3-SAT}$ und $\problem{3-SAT} \redp L$ $\Rightarrow$ $L$
NP-vollständig. & W & $\problem{3-SAT} \redp L$ gibt NP-Schwere;
$L \redp \problem{3-SAT}$ gibt $L \in \NP$. \\
\addlinespace
$L$ NP-vollständig: $L \in \Pclass \iff \Pclass = \NP$. & W & Satz 6.16. \\
\addlinespace
Es ist möglich, dass $\problem{3-SAT} \in \Pclass$ und
$\problem{Clique} \notin \Pclass$. & F & $\problem{Clique} \redp
\problem{3-SAT}$ (3-SAT ist NP-vollständig); aus $\problem{3-SAT} \in \Pclass$
folgt $\problem{Clique} \in \Pclass$. \\
\addlinespace
Wenn die ETH falsch ist, gilt $\Pclass = \NP$. & F & ETH falsch heißt nur:
3-SAT in $2^{o(n)}$ -- das kann immer noch superpolynomiell sein
(z.\,B. $2^{\sqrt{n}}$). Umgekehrt gilt aber: $\Pclass = \NP \Rightarrow$ ETH
falsch. \\
\bottomrule
\end{tabular}
\end{center}
{\footnotesize $^*$ genauer: nicht beweisbar wahr; äquivalent zu $\Pclass = \NP$.}

\begin{merke}
\textbf{Weiter geht's mit Uebung.pdf:} Dort stehen die Schritt-für-Schritt-Rezepte
für alle sechs Klausur-Aufgabentypen, die vier Vorlesungsbeweise in voller
Länge, alle Reduktionen der Serien mit Musterbeweis -- und Selbsttest-Aufgaben
aus echten Klausuren.
\end{merke}

\end{document}