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

% etwas luftigerer Satz fuer Lesbarkeit
\linespread{1.05}
\setlength{\parskip}{0.4em}

\title{\textbf{\Huge Komplexität verstehen}\\[0.5em]
\large Der ausführliche, grafische Guide zu\\
\textit{Analyse von Algorithmen und Komplexität}\\[0.3em]
\normalsize CAU Kiel -- Sommersemester 2026 \quad$\cdot$\quad Ausgabe 4}
\author{}
\date{}

\begin{document}
\maketitle
\thispagestyle{empty}

\begin{center}\itshape\large
Nicht auswendig lernen -- verstehen.\\
Jeder Begriff mit Bild, Beispiel und einer Frage zum Selberdenken.
\end{center}

\vfill

\noindent\textbf{Was dieser Guide ist.}
Ein Heft, das dir das \emph{Fundament} des Kurses aufbaut -- gründlich, in Ruhe,
mit vielen Bildern. Kein Nachschlagewerk zum Überfliegen. Wir nehmen uns für
jeden Gedanken den Platz, den er braucht. Wenn du es durcharbeitest, verstehst
du den ganzen Stoff und siehst, wie alles zusammenhängt.

\medskip
\noindent\textbf{So arbeitest du damit.}
Lies langsam. Schau dir jedes Bild an und frag dich, was es zeigt, bevor du
weiterliest. Am Ende jedes Kapitels stehen \textbf{Abruf-Fragen}: Beantworte sie
\emph{schriftlich aus dem Kopf}, \emph{bevor} du im Lösungsteil
(Anhang~\ref{sec:loesungen}) nachsiehst. Dieses aktive Erinnern ist der
eigentliche Lerneffekt.

\medskip
\noindent\textbf{Die Kästen.}
\begin{center}\small
\begin{tabular}{ll}
\ding{72}~Intuition & die Idee in einfachen Worten\\
\ding{43}~Analogie & ein Bild aus dem Alltag\\
\ding{110}~Definition & die präzise Fassung\\
\ding{115}~Satz & ein Ergebnis mit erklärter Beweis\emph{idee}\\
\ding{108}~Beispiel & durchgerechnet, mit echten Zahlen\\
\ding{52}~Warum in NP? & Zertifikat und Prüfung des Problems\\
\ding{43}~Idee & die Konstruktion hinter einer Reduktion/einem Beweis\\
\ding{73}~Aha & die Pointe\\
\ding{55}~Stolperstein & der häufige Fehler\\
\ding{228}~Zusammenhang & wie es ins Ganze passt\\
\textbf{?}~Abruf & prüfe dich -- Lösung nur im Anhang\\
\end{tabular}
\end{center}

\vfill
\newpage
\tableofcontents
\newpage

% ##################################################################
\section{Ein Problem, das sich wehrt}
% ##################################################################

\begin{ziel}
Wir treffen ein Problem, das harmlos aussieht und trotzdem jeden Computer
überfordert. Daran wirst du sehen, warum es überhaupt eine Theorie der
\glqq schweren\grqq{} Probleme braucht.
\end{ziel}

\subsection{Ein Graph ist ein Netz aus Punkten und Linien}

Bevor wir zum Problem kommen, das Vokabular. Ein \emph{Graph} ist einfach ein
Netz: eine Menge von Punkten, die \emph{Knoten}, und Verbindungslinien zwischen
manchen von ihnen, die \emph{Kanten}. Mehr steckt zunächst nicht dahinter. Ein
Graph kann ein Straßennetz sein, ein Freundeskreis, ein Stromnetz -- die
Mathematik dahinter ist dieselbe.

Wir stellen uns die Knoten als \emph{Gäste auf einer Party} vor. Eine Kante
zwischen zwei Gästen heißt: \glqq die beiden kennen sich\grqq.

\subsection{Was ist eine Clique?}

\begin{defn}{Clique}
Eine \emph{Clique} ist eine Gruppe von Knoten, in der \emph{jeder mit jedem}
direkt verbunden ist. Auf der Party: eine Gruppe von Gästen, die sich
\emph{alle} gegenseitig kennen.
\end{defn}

Das \emph{Cliquenproblem} fragt: Gibt es in einem gegebenen Graphen eine Clique
aus mindestens $k$ Knoten? Sieh dir ein kleines Beispiel an und überzeuge dich,
dass du \glqq Clique\grqq{} verstanden hast.

\begin{bsp}{Eine Clique mit dem Auge finden}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(5,3)(-0.6,-0.5)
\put(0,1){\circle*{0.15}}\put(-0.5,1){\small $1$}
\put(1.2,2.4){\circle*{0.15}}\put(1.1,2.6){\small $2$}
\put(2.4,1){\circle*{0.15}}\put(2.55,1){\small $3$}
\put(1.6,-0.2){\circle*{0.15}}\put(1.5,-0.55){\small $4$}
\put(3.6,0.3){\circle*{0.15}}\put(3.75,0.2){\small $5$}
\qbezier(0,1)(0.6,1.7)(1.2,2.4)    % 1-2
\put(0,1){\line(1,0){2.4}}         % 1-3
\qbezier(1.2,2.4)(1.8,1.7)(2.4,1)  % 2-3
\qbezier(2.4,1)(2.0,0.4)(1.6,-0.2) % 3-4
\qbezier(2.4,1)(3.0,0.65)(3.6,0.3) % 3-5
\end{picture}
\end{center}
Die Gruppe $\{1,2,3\}$ bildet ein Dreieck: die Kanten 1--2, 1--3 und 2--3 sind
alle da. Also kennen sich alle drei gegenseitig -- eine Clique der Größe~3.
Die Gruppe $\{2,3,4\}$ ist \emph{keine} Clique: zwischen 2 und 4 gibt es keine
Kante. Und eine Clique aus vier Gästen existiert hier gar nicht -- probiere es
aus.
\end{bsp}

Bei fünf Gästen erkennst du die Antwort auf einen Blick. Ein Computer
\glqq sieht\grqq{} den Graphen aber nicht als Bild. Er muss die Clique
\emph{ausrechnen}. Und genau das wird ab ein paar hundert Gästen zum Problem.

\subsection{Der naheliegende Algorithmus -- und warum er scheitert}

Wie würde ein Computer eine $k$-Clique suchen, wenn er keinen cleveren Trick
kennt? Er würde stur \emph{jede mögliche Gruppe} aus $k$ Gästen bilden und für
jede prüfen, ob sich wirklich alle kennen. Das ist korrekt -- es findet die
Clique garantiert, falls es eine gibt. Aber es ist entsetzlich langsam. Der
Grund liegt in der schieren \emph{Anzahl} der Gruppen.

Nehmen wir $n$ Gäste und suchen eine Clique der Größe $k = n/2$. Die Anzahl der
Gruppen ist dann \glqq $n$ über $n/2$\grqq, und das ist mindestens $2^{n/2}$.
Diese Zahl wächst \emph{explosionsartig}. Schau dir an, wie schnell:

\begin{bsp}{$2^{n/2}$ in Zahlen -- die Explosion}
\begin{center}
\begin{tabular}{rrl}
\toprule
Gäste $n$ & Gruppen (mind.) & Was das bedeutet\\
\midrule
$20$  & rund $1\,000$          & sofort erledigt\\
$40$  & rund $1$ Million        & noch ein Wimpernschlag\\
$100$ & rund $10^{15}$          & über ein Monat bei einer Milliarde/s\\
$200$ & rund $10^{30}$          & länger als das Universum existiert\\
\bottomrule
\end{tabular}
\end{center}
Von 100 auf 200 Gäste wird die Aufgabe nicht doppelt so schwer, sondern um den
Faktor $10^{15}$ schwerer.
\end{bsp}

Der Kern des Problems: Jeder \emph{einzelne} zusätzliche Gast \emph{verdoppelt}
ungefähr die Arbeit. Diese Art von Wachstum heißt \emph{exponentiell}, und sie
ist der natürliche Feind jeder Berechnung. Das folgende Bild stellt sie einem
gutmütigen \emph{polynomiellen} Wachstum ($n^3$) gegenüber.

\begin{bsp}{Zwei Welten: $n^3$ gegen $2^{n/2}$}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(10,5)(-0.7,-0.6)
\put(0,0){\vector(1,0){9.2}} \put(8.8,-0.5){\small Eingabegröße $n$}
\put(0,0){\vector(0,1){4.5}} \put(-0.6,4.3){\small Rechenzeit}
% polynomiell
\qbezier(0,0)(5,0.5)(9,2.0) \put(8.2,2.1){\small $n^3$}
\put(6.2,1.0){\small \itshape harmlos, bleibt flach}
% exponentiell
\qbezier(0,0)(3.0,0.15)(4.0,4.4) \put(3.7,4.4){\small $2^{n/2}$}
\put(4.3,3.3){\small \itshape schießt senkrecht hoch}
% Machbarkeitslinie
\multiput(0,3.4)(0.35,0){24}{\line(1,0){0.18}}
\put(5.6,3.55){\small \itshape Grenze des praktisch Machbaren}
\end{picture}
\end{center}
Die polynomielle Kurve bleibt lange in Bodennähe. Die exponentielle durchbricht
schon bei kleiner Eingabe jede Zeitgrenze und ist danach nicht mehr einzufangen.
\end{bsp}

\begin{intuition}
Warum hilft schnellere Hardware nicht? Ein doppelt so schneller Computer
schafft beim exponentiellen Algorithmus genau \emph{einen} Gast mehr -- weil ein
Gast mehr die Arbeit verdoppelt und die schnellere Hardware genau diese eine
Verdopplung ausgleicht. Willst du zehn Gäste mehr, brauchst du einen
\emph{tausendfach} schnelleren Rechner. Exponentielles Wachstum kann keine
Hardware der Welt einholen.
\end{intuition}

\begin{satz}{Der naive Clique-Algorithmus ist exponentiell}
Für $k = |V|/2$ braucht er mindestens $2^{|V|/2}$ Schritte.\\[0.3em]
\emph{Woran das liegt:} Es gibt $\binom{n}{n/2} \ge 2^{n/2}$ Gruppen der Größe
$n/2$, und jede davon muss wenigstens angefasst werden. Schon das Aufzählen so
vieler Gruppen kostet exponentiell viel Zeit.
\end{satz}

\subsection{Die Frage, die den ganzen Kurs trägt}

Vielleicht ist der naive Algorithmus einfach nur ungeschickt. Vielleicht gibt es
einen raffinierten Weg, die Clique \emph{schnell} zu finden, ohne alle Gruppen
durchzuprobieren?

Für das Cliquenproblem hat bis heute \emph{niemand} so einen Weg gefunden. Und
-- das ist der eigentliche Punkt -- niemand hat auch \emph{bewiesen}, dass es
keinen gibt. Wir stecken in einer Wissenslücke fest.

\begin{aha}
Die Komplexitätstheorie stellt nicht die Frage \glqq Wie löse ich dieses
Problem schnell?\grqq. Sie stellt die tiefere Frage: \glqq Ist dieses Problem
\emph{überhaupt} schnell lösbar -- oder gehört es zu einer großen Familie von
Problemen, die alle gemeinsam schwer sind?\grqq{} Die erste Frage ist offen. Die
zweite können wir beantworten. Genau darum geht es im ganzen Kurs.
\end{aha}

\begin{abruf}
\textbf{A1.} Erkläre in eigenen Worten, warum ein 1000-mal schnellerer Computer
den naiven Clique-Algorithmus kaum brauchbarer macht.\\
\textbf{A2.} Was ist der Unterschied zwischen \glqq wir kennen keinen schnellen
Algorithmus\grqq{} und \glqq es gibt keinen\grqq? Welcher der beiden Fälle ist
für die Clique bewiesen?
\end{abruf}

% ##################################################################
\section{Was heißt eigentlich \glqq schnell\grqq?}
% ##################################################################

\begin{ziel}
Wir machen \glqq schnell\grqq{} präzise. Das führt uns zur ersten großen Klasse:
$\Pclass$, die Probleme, die wir effizient lösen können.
\end{ziel}

\subsection{Geschwindigkeit misst man in der Eingabegröße}

Es ergibt keinen Sinn zu sagen, ein Algorithmus brauche \glqq drei Sekunden\grqq.
Drei Sekunden wofür -- für zehn Zahlen oder für zehn Milliarden? Sinnvoll ist
nur eine Aussage \emph{relativ zur Größe der Eingabe}. Wir schreiben $n$ für
diese Größe und fragen: Wie viele Rechenschritte braucht der Algorithmus im
schlimmsten Fall bei Eingabegröße $n$?

Warum der \emph{schlimmste} Fall? Weil wir eine \emph{Garantie} wollen. Ein
Algorithmus, der meistens schnell ist, aber bei ungünstigen Eingaben
explodiert, gibt uns keine Sicherheit. Der schlimmste Fall über alle Eingaben
der Größe $n$ ist die ehrliche Messgröße.

\subsection{Die Klasse P}

\begin{defn}{Klasse P}
$\Pclass$ ist die Menge aller Entscheidungsprobleme, die ein Algorithmus in
\emph{polynomieller} Zeit löst -- also mit einer Laufzeit von der Form $O(n^d)$,
wobei $d$ eine feste Zahl ist ($n$, $n^2$, $n^3$, \dots). Kurz gesagt: die
\emph{effizient lösbaren} Probleme.
\end{defn}

Beispiele, für die wir schnelle, polynomielle Algorithmen kennen: Zahlen
sortieren, den kürzesten Weg in einem Straßennetz finden, ein Stromnetz mit
minimalen Kosten aufspannen (minimaler Spannbaum), Paare optimal zuordnen
(Matching). All das liegt in $\Pclass$.

\begin{intuition}
\glqq Polynomiell = effizient\grqq{} ist eine \emph{Vereinbarung}, kein
Naturgesetz. Ein Algorithmus mit Laufzeit $n^{100}$ wäre praktisch nutzlos, zählt
aber formal als polynomiell. Trotzdem funktioniert die Vereinbarung erstaunlich
gut: Polynomielle Algorithmen aus der Praxis haben fast immer kleine Exponenten,
und die Grenze \glqq polynomiell gegen exponentiell\grqq{} bleibt dieselbe, egal
welchen realistischen Rechnertyp man zugrunde legt. Diese Robustheit macht sie
zur richtigen Trennlinie.
\end{intuition}

\subsection{Warum wir alles als Ja/Nein-Frage schreiben}

Ein Detail, das anfangs überrascht: Die Theorie behandelt fast nur
\emph{Entscheidungsprobleme} -- Fragen mit Antwort \glqq Ja\grqq{} oder
\glqq Nein\grqq. Statt \glqq Wie groß ist die größte Clique?\grqq{} fragt man
\glqq Gibt es eine Clique mit mindestens $k$ Knoten?\grqq.

Das wirkt wie ein Verlust an Information, ist aber keiner.

\begin{analogie}
Es ist wie beim Abwiegen ohne Anzeige, nur mit der Frage \glqq schwerer als
$x$?\grqq. Fragst du \glqq schwerer als 1\,kg? als 2\,kg? als 3\,kg?\grqq{} und
so weiter, tastest du das genaue Gewicht ein. Die Ja/Nein-Frage für \emph{jede}
Schranke trägt also dieselbe Information wie die genaue Zahl. Deshalb ist die
Ja/Nein-Version eines Problems \glqq gleich schwer\grqq{} wie die
Optimierungsversion -- aber viel einfacher sauber zu vergleichen.
\end{analogie}

Formal kodiert man jede Eingabe als Zeichenkette (ein \emph{Wort}) über einem
Alphabet, und ein Problem wird zur \emph{Menge aller Ja-Wörter}. Du musst diese
Brille nicht ständig tragen. Merke dir nur den Kern: \emph{Ein Problem ist die
Menge seiner Ja-Eingaben.} Beim Cliquenproblem ist das die Menge aller Paare
$(G,k)$, für die $G$ tatsächlich eine $k$-Clique besitzt.

\subsection{Ein Stolperstein, der später wichtig wird}

\begin{stolper}
\textbf{Zahlen sind binär kodiert -- und dadurch \glqq riesig\grqq{} gegenüber
ihrer Länge.} Eine Zahl $K$ steht als Eingabe nur mit ihren Ziffern da, also mit
Länge etwa $\log K$. Ihr \emph{Wert} $K$ ist aber exponentiell größer als diese
Länge. Ein Algorithmus, der \glqq von 1 bis $K$ zählt\grqq, macht $K$ Schritte --
und das ist exponentiell in der Eingabelänge, nicht polynomiell. An diesem
scheinbar harmlosen Punkt hängt später, warum \problem{SubSet Sum} schwer ist und
was das Wort \glqq pseudopolynomiell\grqq{} bedeutet. Merk ihn dir.
\end{stolper}

\begin{abruf}
\textbf{A3.} Ist ein Algorithmus mit Laufzeit $n^4$ \glqq effizient\grqq{} im
Sinne der Theorie? Begründe.\\
\textbf{A4.} \glqq Zähle von 1 bis zur eingegebenen Zahl $K$\grqq{} sieht
kinderleicht aus. Warum ist dieser Algorithmus trotzdem \emph{nicht}
polynomiell?
\end{abruf}

% ##################################################################
\section{Prüfen ist leichter als Lösen}
% ##################################################################

\begin{ziel}
Wir entdecken die zentrale Beobachtung der Theorie: Für viele schwere Probleme
ist es hart, eine Lösung zu \emph{finden}, aber leicht, eine vorgelegte Lösung
zu \emph{prüfen}. Daraus entsteht die Klasse $\NP$ -- und ein Rezept, mit dem du
für jedes Problem zeigst, dass es dazugehört.
\end{ziel}

\subsection{Die Sudoku-Beobachtung}

\begin{analogie}
Stell dir ein schweres Sudoku vor. Es zu \emph{lösen} kann eine halbe Stunde
dauern. Aber wenn dir jemand ein fertig ausgefülltes Gitter hinlegt und fragt
\glqq stimmt das?\grqq, brauchst du eine Minute: Du prüfst jede Zeile, jede
Spalte, jeden Block. \emph{Lösen ist schwer, Prüfen ist leicht.} Diese
Asymmetrie ist der ganze Kern von $\NP$.
\end{analogie}

Genau so ist es bei der Clique. Eine Clique zu \emph{finden} ist mühsam. Aber
wenn dir jemand eine Gruppe von Gästen nennt und behauptet \glqq die bilden eine
Clique\grqq, prüfst du das im Handumdrehen: Du schaust für jedes Paar nach, ob
die Kante da ist. Die vorgelegte Gruppe ist der Beweis -- wir nennen sie ein
\emph{Zertifikat}.

\subsection{Zertifikat und Verifizierer}

\begin{defn}{Verifizierer und Zertifikat}
Ein \emph{Verifizierer} für ein Problem $L$ ist ein Algorithmus $A$, der
\emph{zwei} Dinge bekommt: die eigentliche Frage (die Instanz $x$) und einen
Lösungsvorschlag $c$. Er soll erfüllen:
\[
x \in L \quad\Longleftrightarrow\quad \text{es gibt ein } c \text{ mit } A(x,c)=1.
\]
Der Vorschlag $c$ heißt \emph{Zertifikat}.
\end{defn}

Lies die beiden Richtungen einzeln, sie sind beide wichtig:
\begin{itemize}
\item Ist $x$ eine \emph{Ja}-Instanz, dann \emph{gibt es} ein Zertifikat, das
$A$ überzeugt.
\item Ist $x$ eine \emph{Nein}-Instanz, dann überzeugt $A$ \emph{kein}
Zertifikat -- egal, was man ihm vorlegt.
\end{itemize}

\begin{defn}{Die Klasse NP}
$\NP$ ist die Menge aller Probleme, die einen Verifizierer besitzen, der ein
\emph{polynomiell langes} Zertifikat in \emph{polynomieller} Zeit prüft.
\end{defn}

\begin{intuition}
$\NP$ heißt \glqq effizient \emph{überprüfbar}\grqq, nicht \glqq effizient
\emph{lösbar}\grqq. Das ist der ganze Witz. Eine Lösung zu finden mag
exponentiell teuer sein -- aber \emph{hätte} man sie, wäre die Kontrolle billig.
Das Zertifikat ist die kurze Antwort auf die Frage \glqq und woher weiß ich,
dass das stimmt?\grqq.
\end{intuition}

\subsection{Der NP-Dreischritt: so beweist man \glqq $\in\NP$\grqq}

Für \emph{jedes} Problem läuft der Nachweis \glqq liegt in $\NP$\grqq{} nach
demselben Muster ab. Dieses Rezept begegnet dir im ganzen Kurs, also lohnt es
sich, es einmal in Ruhe anzusehen.

\begin{idee}{Der NP-Dreischritt}
\textbf{(1) Zertifikat benennen.} Was ist die \glqq Lösung\grqq{} des Problems?
Eine Teilmenge, eine Belegung, eine Reihenfolge? Sag außerdem, dass sie
polynomiell lang ist (sonst könnte man sie nicht schnell lesen).\\[0.4em]
\textbf{(2) Verifizierer beschreiben.} Ein Algorithmus, der \emph{alle}
geforderten Eigenschaften prüft. Dazu gehören immer drei Punkte:
\begin{itemize}
\item die Prüfschritte selbst,
\item die Korrektheit in \emph{beiden} Richtungen (Ja-Instanz $\Rightarrow$ ein
Zertifikat wird akzeptiert; Nein-Instanz $\Rightarrow$ keines),
\item die Laufzeit, konkret als $O(\cdot)$.
\end{itemize}
\textbf{(3) Alternativ: die Rate-Sicht.} Man darf $\NP$ auch über eine
\glqq ratende\grqq{} Maschine beschreiben, die die Lösung errät und dann prüft.
Die Rateschritte \emph{sind} das Zertifikat -- es ist nur eine andere Sprache
für dieselbe Sache.
\end{idee}

Machen wir den Dreischritt einmal ganz konkret.

\begin{bsp}{Der NP-Dreischritt für Clique}
\textbf{Zertifikat:} eine Knotenmenge $C$ (etwa als Liste der gewählten
Knoten). Sie ist höchstens so lang wie die Knotenzahl, also polynomiell.\\[0.3em]
\textbf{Verifizierer:} Prüfe zwei Dinge -- erstens, ob wirklich \emph{jedes}
Paar aus $C$ durch eine Kante verbunden ist (das kostet $O(|C|^2)$ Blicke in
die Kantenliste); zweitens, ob $|C| \ge k$ ist ($O(|V|)$).\\[0.3em]
\textbf{Korrektheit:} Gibt es eine $k$-Clique, so ist genau sie ein Zertifikat,
das akzeptiert wird. Gibt es keine, scheitert jeder Vorschlag an der
Paar-Prüfung. Beide Richtungen stimmen.\\[0.3em]
\textbf{Laufzeit:} polynomiell. Also liegt \problem{Clique} in $\NP$.
\end{bsp}

\subsection{Die zweite Sicht: Raten}

\begin{intuition}
Die dritte Zeile des Dreischritts verdient einen eigenen Gedanken. Stell dir
einen Algorithmus vor, der an jeder Verzweigung nicht \emph{eine} Möglichkeit
wählt, sondern \emph{alle gleichzeitig} verfolgt -- wie ein Läufer, der sich an
jeder Kreuzung in Kopien aufteilt und jede Kopie einen Weg gehen lässt. So ein
Algorithmus heißt \emph{nichtdeterministisch}. Er \glqq akzeptiert\grqq, wenn
\emph{irgendeine} Kopie ans Ziel kommt. Für eine Nein-Instanz kommt keine Kopie
an. \glqq Richtig raten\grqq{} und \glqq ein Zertifikat geschenkt bekommen\grqq{}
sind zwei Namen für genau dieselbe Fähigkeit.
\end{intuition}

\subsection{P steckt in NP -- und die Millionenfrage}

\begin{satz}{$\Pclass \subseteq \NP$}
Jedes effizient \emph{lösbare} Problem ist auch effizient \emph{überprüfbar}.\\[0.3em]
\emph{Warum:} Wenn du ein Problem selbst schnell lösen kannst, brauchst du das
Zertifikat gar nicht. Du ignorierst es und rechnest die Antwort direkt aus. Der
Löser ist damit ein besonders fauler Verifizierer.
\end{satz}

Die spannende Frage ist die \emph{Umkehrung}: Ist auch alles, was man schnell
\emph{prüfen} kann, schnell \emph{lösbar}? Gilt also $\Pclass = \NP$?

\begin{aha}
Ob $\Pclass = \NP$ gilt, weiß bis heute niemand. Es ist eines der sieben
Millennium-Probleme, ausgelobt mit einer Million Dollar. Die meisten Fachleute
vermuten $\Pclass \ne \NP$ -- dass Prüfen also \emph{echt} leichter ist als
Lösen. Beweisen konnte es keiner. Und der ganze Rest dieses Kurses --
NP-Vollständigkeit, ETH, Approximation -- ist nichts anderes als der kluge
Umgang mit genau dieser Unwissenheit.
\end{aha}

\begin{abruf}
\textbf{A5.} Führe den NP-Dreischritt für \problem{Vertex Cover} durch: Was ist
das Zertifikat, was prüft der Verifizierer, wie lange dauert das?\\
\textbf{A6.} Warum bedeutet \glqq $L$ hat einen polynomiellen Verifizierer\grqq{}
nicht dasselbe wie \glqq $L$ ist in Polynomialzeit lösbar\grqq?
\end{abruf}

% ##################################################################
\section{Reduktionen: Probleme miteinander vergleichen}
% ##################################################################

\begin{ziel}
Jetzt kommt das wichtigste Werkzeug des ganzen Kurses. Mit der \emph{Reduktion}
vergleichst du zwei Probleme nach Schwierigkeit -- und zwar, ohne für auch nur
eines von beiden einen Algorithmus zu kennen. Das klingt paradox. Wir bauen es
langsam auf.
\end{ziel}

\subsection{Die Grundidee: ein Problem durch ein anderes lösen}

Angenommen, du hast ein fertiges Werkzeug für Problem $B$ -- eine Maschine, in
die du eine $B$-Frage steckst und die Ja oder Nein ausspuckt. Jetzt stehst du
vor Problem $A$, für das du \emph{kein} Werkzeug hast. Kannst du $A$ trotzdem
lösen?

Ja -- \emph{falls} du jede $A$-Frage so \emph{umformen} kannst, dass die
$B$-Maschine sie beantwortet. Dann löst du $A$ über den Umweg $B$: erst
umformen, dann die $B$-Maschine fragen, deren Antwort ist auch die Antwort auf
deine $A$-Frage.

\begin{analogie}
Du möchtest wissen, ob eine Strecke länger als eine Meile ist, hast aber nur ein
Lineal mit Kilometer-Skala. Kein Problem: Du rechnest die Frage \glqq länger als
1 Meile?\grqq{} um in \glqq länger als $1{,}609$\,km?\grqq{} und misst dann mit
dem km-Lineal. Die \emph{Umrechnung} ist billig, das eigentliche \emph{Messen}
erledigt das fremde Werkzeug. Genau so arbeitet eine Reduktion: billiges
Umformen plus fremder Löser.
\end{analogie}

\subsection{Die präzise Definition}

\begin{defn}{Polynomielle Reduktion $A \redp B$}
Eine \emph{Reduktion} von $A$ auf $B$ ist eine Funktion $f$, die jede
$A$-Eingabe $w$ in eine $B$-Eingabe $f(w)$ übersetzt, sodass die Antworten
zusammenpassen:
\[
w \in A \quad\Longleftrightarrow\quad f(w) \in B.
\]
Sie heißt \emph{polynomiell}, wenn ein Algorithmus $f(w)$ in polynomieller Zeit
berechnet. Wir schreiben dann $A \redp B$.
\end{defn}

Die Bedingung $w \in A \iff f(w) \in B$ verlangt \emph{beide} Richtungen: Aus
einer Ja-Instanz von $A$ wird eine Ja-Instanz von $B$, und aus einer
Nein-Instanz von $A$ wird eine Nein-Instanz von $B$. Nur so bleibt die Antwort
erhalten. Das folgende Bild zeigt den Datenfluss, wenn man mit einer Reduktion
das Problem $A$ über einen $B$-Löser knackt.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(13.5,2.2)(0,-0.4)
\put(0,0.3){\framebox(2.4,1.1){\shortstack{\small $A$-Frage\\ \small $w$}}}
\put(2.4,0.85){\vector(1,0){1.6}}
\put(2.45,1.05){\small $f$ (billig)}
\put(4.0,0.3){\framebox(2.6,1.1){\shortstack{\small $B$-Frage\\ \small $f(w)$}}}
\put(6.6,0.85){\vector(1,0){1.6}}
\put(6.7,1.05){\small $B$-Löser}
\put(8.2,0.3){\framebox(2.2,1.1){\shortstack{\small Ja /\\ \small Nein}}}
\put(10.4,0.85){\vector(1,0){1.5}}
\put(10.5,1.05){\small ist auch}
\put(11.9,0.3){\framebox(1.6,1.1){\shortstack{\small Antwort\\ \small auf $w$}}}
\end{picture}
\end{center}

\begin{intuition}
Was bedeutet $A \redp B$ inhaltlich? Genau dies: \glqq $B$ ist \emph{mindestens
so schwer} wie $A$.\grqq{} Denn wer $B$ schnell lösen kann, löst mit der
billigen Umformung $f$ auch $A$ schnell. Anders gesagt: Die Schwierigkeit
\emph{fließt entlang des Pfeils}. Wenn $A$ schwer ist, dann kann $B$ nicht leicht
sein -- sonst wäre über den Umweg auch $A$ leicht.
\end{intuition}

\subsection{Die Richtung -- lies das zweimal}

Hier passiert der häufigste und teuerste Fehler im ganzen Kurs. Nimm dir Zeit.

Du willst normalerweise zeigen, dass ein \emph{neues} Problem $Y$ \emph{schwer}
ist. Dazu nimmst du ein Problem $X$, von dem du \emph{schon weißt}, dass es
schwer ist, und reduzierst $X$ \emph{auf} $Y$ -- also $X \redp Y$.

\begin{stolper}
Die Richtung ist \textbf{bekannt schwer $\redp$ neu}, niemals umgekehrt. Die
Reduktion nimmt eine Instanz des \emph{bekannten} Problems und baut daraus eine
Instanz des \emph{neuen}. Warum genau so? Weil $X \redp Y$ bedeutet \glqq $Y$
mindestens so schwer wie $X$\grqq. Da $X$ schon als schwer bekannt ist, erbt $Y$
diese Schwere. Machst du es andersherum ($Y \redp X$), zeigst du nur \glqq $Y$
höchstens so schwer wie das schwere $X$\grqq{} -- und das sagt über $Y$
überhaupt nichts.
\end{stolper}

\begin{analogie}
Du willst beweisen, dass ein neuer Boxer stark ist. Also lässt du den
\emph{amtierenden Champion} gegen ihn antreten. Besiegt der Neue den Champion,
ist er stark. Du würdest nie den Neuen gegen einen \emph{Anfänger} antreten
lassen -- ein Sieg da beweist nichts. \glqq Champion (bekannt stark) gegen
Neuen.\grqq{} Genau das ist $X_{\text{bekannt}} \redp Y_{\text{neu}}$.
\end{analogie}

\subsection{Reduktionen lassen sich verketten}

\begin{satz}{Transitivität}
Gilt $A \redp B$ und $B \redp C$, dann auch $A \redp C$.\\[0.3em]
\emph{Warum:} Man schaltet die beiden Umformungen einfach hintereinander -- erst
$A \to B$, dann $B \to C$. Die Zwischenausgabe ist polynomiell groß, also
bleibt auch die Gesamt-Umformung polynomiell. Zwei billige Schritte ergeben
zusammen einen billigen Schritt.
\end{satz}

Das ist mehr als eine technische Note: Es erlaubt uns, eine ganze \emph{Kette}
von Reduktionen zu bauen. Ist das erste Problem als schwer bekannt, trägt die
Kette diese Schwere Glied für Glied bis ans Ende. Genau diese Kette bauen wir
ab dem nächsten Kapitel auf.

\begin{abruf}
\textbf{A7.} Du weißt, dass \problem{Clique} schwer ist, und willst zeigen, dass
\problem{Vertex Cover} schwer ist. In welche Richtung reduzierst du, und warum
genau so und nicht andersherum?\\
\textbf{A8.} Formuliere in einem Satz, was $A \redp B$ über die relative
Schwierigkeit von $A$ und $B$ aussagt.
\end{abruf}

% ##################################################################
\section{Die härtesten Probleme: NP-vollständig}
% ##################################################################

\begin{ziel}
Mit der Reduktion in der Hand können wir jetzt sagen, was \glqq die schwersten
Probleme in $\NP$\grqq{} genau sind -- und warum ein einziger schneller
Algorithmus für eines von ihnen die gesamte Landschaft zum Einsturz brächte.
\end{ziel}

\subsection{Zwei Begriffe: NP-schwer und NP-vollständig}

\begin{defn}{NP-schwer und NP-vollständig}
\begin{itemize}
\item $L_0$ heißt \emph{NP-schwer}, wenn sich \emph{jedes} Problem $L \in \NP$
auf $L_0$ reduzieren lässt: $L \redp L_0$ für alle $L \in \NP$.
\item $L_0$ heißt \emph{NP-vollständig}, wenn es NP-schwer ist \textbf{und}
selbst in $\NP$ liegt.
\end{itemize}
\end{defn}

\begin{intuition}
Denk an zwei Schranken, die von oben und unten zusammenkommen:
\begin{itemize}
\item \emph{NP-schwer} ist eine \textbf{untere} Schranke -- \glqq mindestens so
schwer wie alles in $\NP$\grqq. Alle NP-Probleme reduzieren auf $L_0$, also ist
$L_0$ mindestens so hart wie jedes von ihnen.
\item \emph{$\in \NP$} ist eine \textbf{obere} Schranke -- \glqq nicht schwerer
als $\NP$\grqq.
\end{itemize}
\emph{NP-vollständig} heißt: beide Schranken treffen sich. Das sind genau die
schwersten Probleme \emph{innerhalb} von $\NP$.
\end{intuition}

\begin{stolper}
NP-schwer heißt \emph{nicht} automatisch \glqq liegt in $\NP$\grqq. Es gibt
Probleme, die NP-schwer sind, aber weit außerhalb von $\NP$ liegen -- das
Halteproblem (Kapitel~\ref{sec:halt}) ist nicht einmal lösbar und trotzdem
NP-schwer. \glqq Schwer\grqq{} und \glqq überhaupt in NP\grqq{} sind zwei
verschiedene Achsen.
\end{stolper}

\subsection{Warum ein Algorithmus für eines alle löst}

\begin{satz}{NP-vollständig verbindet $\Pclass$ und $\NP$}
Ist $L_0$ NP-vollständig, dann gilt: $\Pclass = \NP$ genau dann, wenn
$L_0 \in \Pclass$.\\[0.3em]
\emph{Warum:} Läge $L_0$ in $\Pclass$, könnte man \emph{jedes} $L \in \NP$
effizient lösen -- erst die Reduktion $L \redp L_0$ rechnen, dann den schnellen
$L_0$-Löser anwerfen. Damit läge ganz $\NP$ in $\Pclass$.
\end{satz}

\begin{aha}
Das ist die Sprengkraft der NP-Vollständigkeit. Fände jemand für \emph{ein
einziges} NP-vollständiges Problem einen effizienten Algorithmus, dann wären
\emph{schlagartig alle} Probleme in $\NP$ effizient lösbar -- die Welt wäre eine
andere. Genau deshalb gilt umgekehrt: Solange das niemandem gelingt, ist ein
NP-Vollständigkeitsbeweis das stärkste bekannte Indiz dafür, dass ein Problem
\emph{keinen} effizienten Algorithmus hat.
\end{aha}

\subsection{Der Anker: der Satz von Cook und Levin}

Damit die Reduktionskette überhaupt losgehen kann, braucht man ein
\emph{erstes} NP-vollständiges Problem -- eines, das man von Hand als schwer
nachweist, ohne sich auf ein anderes stützen zu können. Cook und Levin haben es
geliefert. Es heißt \problem{SAT}: Gegeben eine aussagenlogische Formel, gibt es
eine Belegung ihrer Variablen, die sie wahr macht?

\begin{satz}{Cook (1971) und Levin (1973)}
\problem{SAT} ist NP-vollständig -- das \emph{erste} solche Problem.\\[0.3em]
\emph{Die Beweisidee in einem Bild:} Man nimmt ein \emph{beliebiges} Problem
$L \in \NP$ mit seiner ratenden Maschine und \glqq gießt\grqq{} deren Rechnung
in eine große logische Formel. Variablen der Formel beschreiben Aussagen wie
\glqq zur Zeit $t$ ist die Maschine im Zustand $q$\grqq{} oder \glqq zur Zeit $t$
steht auf Bandfeld $i$ das Symbol $a$\grqq. Weitere Teilformeln erzwingen, dass
ein gültiger Rechenablauf beschrieben wird. Das Entscheidende: Eine
\emph{erfüllende Belegung} der Formel entspricht \emph{genau} einem
akzeptierenden Rechenweg der Maschine. Also gilt: $L$-Ja-Instanz $\iff$ Formel
erfüllbar. Da $L$ beliebig war, ist \problem{SAT} schwer für ganz $\NP$.
\end{satz}

Du musst diesen Beweis nicht im Detail beherrschen. Wichtig ist seine Rolle:
\problem{SAT} ist der \emph{Anker}, an dem die ganze Kette hängt. Ab hier
braucht man nie wieder \glqq alle $L \in \NP$\grqq{} zu betrachten.

\subsection{Das Arbeitspferd: das Vererbungskorollar}

\begin{idee}{Vererbungskorollar -- so wächst die Liste}
Um ein \emph{neues} Problem $Y$ als NP-vollständig nachzuweisen, brauchst du nur
zwei Dinge:
\begin{enumerate}
\item eine Reduktion $X \redp Y$ von \emph{einem} bereits bekannten
NP-vollständigen Problem $X$, und
\item den Nachweis $Y \in \NP$ (den NP-Dreischritt aus Kapitel 3).
\end{enumerate}
Dann ist $Y$ automatisch NP-vollständig. Denn für jedes $L \in \NP$ gilt
$L \redp X \redp Y$ (Transitivität) -- also ist $Y$ NP-schwer, und mit
$Y \in \NP$ auch NP-vollständig.
\end{idee}

Kein Wort mehr über \glqq alle $L \in \NP$\grqq. Eine Reduktion, ein
NP-Nachweis -- fertig. Genau so entsteht die folgende Landkarte.

\subsection{Die Landkarte der Schwere}

Alle Probleme des Kurses hängen an \emph{einer} Kette, die bei \problem{SAT}
beginnt. Jeder Pfeil ist eine Reduktion und heißt \glqq wird reduziert auf\grqq;
die Schwere fließt von oben nach unten.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(13,8.7)(0,-0.3)
\put(5.1,7.7){\framebox(2.4,0.7){\textbf{\problem{SAT}}}}
\put(6.3,7.7){\vector(-2,-1){2.6}}
\put(6.3,7.7){\vector(0,-1){1.3}}
\put(6.3,7.7){\vector(2,-1){2.6}}
\put(2.6,5.7){\framebox(2.0,0.7){\problem{3-SAT}}}
\put(5.3,5.7){\framebox(2.0,0.7){\problem{$k$-Clique}}}
\put(8.0,5.7){\framebox(2.0,0.7){\problem{3-DM}}}
\put(3.6,5.7){\vector(0,-1){1.3}}
\put(6.3,5.7){\vector(0,-1){1.3}}
\put(9.0,5.7){\vector(0,-1){1.3}}
\put(2.6,3.7){\framebox(2.0,0.7){\problem{$k$-Color}}}
\put(5.1,3.7){\framebox(2.4,0.7){\problem{IS}, \problem{VC}}}
\put(8.0,3.7){\framebox(2.0,0.7){\problem{3-EC}}}
\put(3.6,3.7){\vector(0,-1){1.3}}
\put(6.3,3.7){\vector(0,-1){1.3}}
\put(9.0,3.7){\vector(0,-1){1.3}}
\put(2.2,1.7){\framebox(2.8,0.7){$\problem{HK}\to\problem{TSP}$}}
\put(5.1,1.7){\framebox(2.4,0.7){\problem{FVS}, $\Delta$-Cover}}
\put(8.0,1.7){\framebox(2.0,0.7){\problem{SubSetSum}}}
\put(9.0,1.7){\vector(0,-1){1.3}}
\put(6.6,0.0){\framebox(3.8,0.7){\problem{Partition}, \problem{Knapsack}, $P\|\Cmax$}}
\end{picture}
\end{center}

Im nächsten Kapitel gehen wir jedes dieser Probleme einzeln durch. Danach
zeichnen wir die wichtigsten Pfeile -- die Reduktionen -- im Detail nach.

\begin{abruf}
\textbf{A9.} Welche zwei Dinge musst du zeigen, um ein neues Problem als
NP-vollständig zu beweisen? Welches der beiden wird am häufigsten vergessen?\\
\textbf{A10.} Warum würde $\Pclass = \NP$ folgen, wenn jemand \problem{SubSet
Sum} in Polynomialzeit löste?
\end{abruf}

% ##################################################################
\section{Der Problem-Zoo}\label{sec:zoo}
% ##################################################################

\begin{ziel}
Wir lernen alle Probleme des Kurses kennen -- jedes einzeln, mit Ruhe. Zu jedem
gibt es die Definition (was gefragt ist) und die Begründung, \emph{warum es in
$\NP$ liegt} (das Zertifikat). Woher die Schwere kommt und wie die Reduktionen
konkret arbeiten, folgt im nächsten Kapitel. Alle diese Probleme sind
NP-vollständig.
\end{ziel}

% ------------------------------------------------------------------
\subsection{SAT -- das Ur-Problem der Logik}
% ------------------------------------------------------------------

\problem{SAT} steht am Anfang von allem. Es geht um aussagenlogische Formeln in
einer festen Form, der \emph{konjunktiven Normalform} (KNF): ein UND von
\emph{Klauseln}, wobei jede Klausel ein ODER von \emph{Literalen} ist. Ein
Literal ist eine Variable $x_j$ oder ihre Verneinung $\neg x_j$.

\begin{defn}{SAT}
Gegeben eine KNF-Formel $\alpha = C_1 \wedge \dots \wedge C_m$. Frage: Gibt es
eine Belegung der Variablen mit wahr/falsch, die die ganze Formel wahr macht
(also \emph{jede} Klausel erfüllt)?
\end{defn}

\begin{bsp}{SAT von Hand lösen}
$\alpha = (x_1 \vee x_{10}) \wedge (x_1 \vee \neg x_{10}) \wedge (x_{10})$.
Die dritte Klausel besteht nur aus $x_{10}$ -- sie zwingt $x_{10} = \true$.
Damit die zweite Klausel $(x_1 \vee \neg x_{10})$ wahr wird und $\neg x_{10}$
nun falsch ist, muss $x_1 = \true$ sein. Mit beiden auf wahr ist auch die erste
Klausel erfüllt. Die Formel ist also erfüllbar, Zeuge: $x_1 = x_{10} = \true$.
\end{bsp}

\begin{zert}
\textbf{Zertifikat:} die Belegung $\psi$ (ein Bit pro Variable).
\textbf{Verifizierer:} setze $\psi$ ein und werte jede Klausel aus; akzeptiere,
wenn alle wahr sind. Das kostet lineare Zeit in der Formellänge. Also
$\problem{SAT} \in \NP$.
\end{zert}

% ------------------------------------------------------------------
\subsection{3-SAT -- SAT mit kurzen Klauseln}
% ------------------------------------------------------------------

\begin{defn}{3-SAT}
Wie \problem{SAT}, aber jede Klausel hat \emph{höchstens 3} Literale.
\end{defn}

Warum eine eigene Version? Weil kurze Klauseln viel leichter in andere Probleme
\glqq einzubauen\grqq{} sind. Fast alle späteren Reduktionen starten deshalb bei
\problem{3-SAT}, nicht beim allgemeinen \problem{SAT}. Der NP-Nachweis ist
derselbe wie bei \problem{SAT} (Belegung als Zertifikat).

% ------------------------------------------------------------------
\subsection{Clique, Independent Set, Vertex Cover -- ein Trio}
% ------------------------------------------------------------------

Diese drei Graphprobleme hängen so eng zusammen, dass man sie am besten
gemeinsam versteht. Zuerst jedes für sich.

\begin{defn}{Clique, Independent Set, Vertex Cover}
Gegeben ein Graph $G$ und eine Zahl $k$.
\begin{itemize}
\item \problem{Clique}: eine Knotengruppe, in der \emph{alle} paarweise
verbunden sind -- gibt es eine der Größe $\ge k$?
\item \problem{Independent Set (IS)}: eine Knotengruppe, in der \emph{keine} zwei
verbunden sind -- gibt es eine der Größe $\ge k$?
\item \problem{Vertex Cover (VC)}: eine Knotenmenge, die \emph{jede} Kante
berührt (mindestens ein Endpunkt liegt drin) -- gibt es eine der Größe $\le k$?
\end{itemize}
\end{defn}

\begin{zert}
Für alle drei ist das Zertifikat die \emph{Knotenmenge} selbst.
\textbf{Clique:} prüfe, ob alle Paare verbunden sind. \textbf{IS:} prüfe, ob
kein Paar verbunden ist. \textbf{VC:} prüfe, ob jede Kante einen Endpunkt in der
Menge hat. Dazu jeweils die Größe. Alles in $O(|V|^2)$ bzw. $O(|E|)$ -- also
liegen alle drei in $\NP$.
\end{zert}

Jetzt der Grund, warum man sie zusammen lernt. Es ist \emph{ein und dasselbe
Bild}, nur dreimal anders betrachtet.

\begin{aha}
\textbf{Das Dualitätsdreieck.} Betrachte einen Graphen $G$ und seinen
\emph{Komplementgraphen} $\bar G$ (dieselben Knoten, aber genau die Kanten, die
$G$ \emph{nicht} hat). Dann gilt für jede Knotenmenge $C$:
\[
C \text{ Clique in } G
\;\iff\;
C \text{ Independent Set in } \bar G
\;\iff\;
V \setminus C \text{ Vertex Cover in } \bar G.
\]
Wer eines der drei versteht, versteht alle drei.
\end{aha}

Das folgende Bild macht es greifbar: links ein Graph $G$, in dem $\{1,2,3\}$
eine Clique ist; rechts sein Komplement $\bar G$, in dem dieselbe Menge
$\{1,2,3\}$ ein Independent Set ist -- und der übrige Knoten $\{4\}$ ein Vertex
Cover.

\begin{bsp}{Ein Bild, drei Rollen}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(12,3.2)(0,-0.5)
% G links
\put(1.3,2.6){\small $G$: $\{1,2,3\}$ ist \emph{Clique}}
\put(1,0){\circle*{0.15}}\put(0.6,-0.05){\small $1$}
\put(1,1.7){\circle*{0.15}}\put(0.6,1.65){\small $2$}
\put(2.5,0.85){\circle*{0.15}}\put(2.65,0.8){\small $3$}
\put(3.9,0.85){\circle*{0.15}}\put(4.05,0.8){\small $4$}
\put(1,0){\line(0,1){1.7}}            % 1-2
\qbezier(1,0)(1.75,0.42)(2.5,0.85)    % 1-3
\qbezier(1,1.7)(1.75,1.27)(2.5,0.85)  % 2-3
% Gbar rechts
\put(7.0,2.6){\small $\bar G$: $\{1,2,3\}$ ist \emph{IS}, $\{4\}$ ist \emph{VC}}
\put(7,0){\circle*{0.15}}\put(6.6,-0.05){\small $1$}
\put(7,1.7){\circle*{0.15}}\put(6.6,1.65){\small $2$}
\put(8.5,0.85){\circle*{0.15}}\put(8.2,1.0){\small $3$}
\put(10,0.85){\circle*{0.15}}\put(10.15,0.8){\small $4$}
\qbezier(7,0)(8.5,0.42)(10,0.85)      % 1-4
\qbezier(7,1.7)(8.5,1.27)(10,0.85)    % 2-4
\put(8.5,0.85){\line(1,0){1.5}}       % 3-4
\end{picture}
\end{center}
In $\bar G$ sind genau die Nicht-Kanten von $G$ eingezeichnet. $\{1,2,3\}$ hat
dort keine innere Kante mehr (Independent Set). Und Knoten 4 allein berührt alle
drei Kanten von $\bar G$ (Vertex Cover).
\end{bsp}

% ------------------------------------------------------------------
\subsection{$k$-Color -- die Landkarten-Färbung}
% ------------------------------------------------------------------

\begin{defn}{$k$-Color}
Gegeben ein Graph $G$ und eine Zahl $k$. Kann man jedem Knoten eine von $k$
Farben geben, sodass \emph{keine Kante} zwei gleichfarbige Enden verbindet?
\end{defn}

Man denkt an eine Landkarte, deren Länder so gefärbt werden, dass keine zwei
Nachbarn dieselbe Farbe tragen. Schon $k = 3$ ist NP-vollständig.

\begin{bsp}{Eine gültige 3-Färbung}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(4.5,2.6)(-0.3,-0.3)
\put(0,0){\circle*{0.18}}\put(-0.35,-0.05){\small $r$}
\put(2,0){\circle*{0.18}}\put(2.1,-0.05){\small $g$}
\put(1,1.7){\circle*{0.18}}\put(1.1,1.7){\small $b$}
\put(3.4,0.85){\circle*{0.18}}\put(3.5,0.8){\small $r$}
\put(0,0){\line(1,0){2}}              % r-g
\qbezier(0,0)(0.5,0.85)(1,1.7)        % r-b
\qbezier(2,0)(1.5,0.85)(1,1.7)        % g-b
\qbezier(2,0)(2.7,0.42)(3.4,0.85)     % g-(r)
\end{picture}
\end{center}
Drei Farben $r,g,b$. Jede Kante verbindet zwei \emph{verschiedene} Farben --
das Dreieck braucht alle drei, der rechte Knoten darf wieder $r$ sein, weil er
nur mit $g$ benachbart ist.
\end{bsp}

\begin{zert}
\textbf{Zertifikat:} die Färbung $f$ (eine Farbe pro Knoten).
\textbf{Verifizierer:} gehe alle Kanten durch und prüfe, ob ihre Enden
verschiedene Farben haben -- $O(|E|)$. Also $\problem{$k$-Color} \in \NP$.
\end{zert}

% ------------------------------------------------------------------
\subsection{Hamiltonkreis -- die Rundreise durch alle Knoten}
% ------------------------------------------------------------------

\begin{defn}{Hamiltonkreis (HK)}
Gegeben ein Graph $G$. Gibt es einen Rundweg, der \emph{jeden} Knoten
\emph{genau einmal} besucht und wieder am Start endet?
\end{defn}

\begin{bsp}{Ein Hamiltonkreis}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(4,2.8)(-0.4,-0.3)
\put(0,0){\circle*{0.15}}
\put(3,0){\circle*{0.15}}
\put(3,2){\circle*{0.15}}
\put(0,2){\circle*{0.15}}
\put(1.5,2.6){\circle*{0.15}}
\linethickness{1.2pt}
\put(0,0){\line(1,0){3}}       % unten
\put(3,0){\line(0,1){2}}       % rechts
\qbezier(3,2)(2.25,2.3)(1.5,2.6) % rechts-oben zur Spitze
\qbezier(1.5,2.6)(0.75,2.3)(0,2) % Spitze zu links-oben
\put(0,2){\line(0,-1){2}}       % links
\end{picture}
\end{center}
Der fette Weg besucht alle fünf Knoten genau einmal und schließt sich -- ein
Hamiltonkreis.
\end{bsp}

\begin{zert}
\textbf{Zertifikat:} die Besuchsreihenfolge (eine Permutation der Knoten).
\textbf{Verifizierer:} prüfe, ob jeder Knoten genau einmal vorkommt und ob jede
aufeinanderfolgende -- und die schließende -- Kante wirklich existiert;
$O(|V|+|E|)$. Also $\problem{HK} \in \NP$.
\end{zert}

% ------------------------------------------------------------------
\subsection{TSP -- die kürzeste Rundreise}
% ------------------------------------------------------------------

\begin{defn}{TSP (Entscheidungsvariante)}
Gegeben Städte mit paarweisen Distanzen $d(i,j)$ und eine Schranke $L$. Gibt es
eine Rundreise durch \emph{alle} Städte (jede genau einmal) mit Gesamtlänge
$\le L$?
\end{defn}

\problem{HK} fragt nur \glqq gibt es überhaupt eine Rundreise?\grqq;
\problem{TSP} fügt Distanzen und eine Längengrenze hinzu. Als
Optimierungsproblem (\glqq finde die kürzeste Rundreise\grqq) ist \problem{TSP}
der Star des Approximationskapitels.

\begin{zert}
\textbf{Zertifikat:} die Reihenfolge der Städte. \textbf{Verifizierer:} addiere
die Distanzen entlang der Rundreise und vergleiche mit $L$; prüfe, dass jede
Stadt genau einmal vorkommt. Linear. Also $\problem{TSP} \in \NP$.
\end{zert}

% ------------------------------------------------------------------
\subsection{Die Mengen- und Zahlprobleme}
% ------------------------------------------------------------------

Die letzte Familie verlässt die Graphen und arbeitet mit Mengen und Zahlen. Wir
stellen sie kurz nacheinander vor; ihr NP-Nachweis ist überall gleich einfach.

\begin{defn}{3-DM, 3-EC, SubSet Sum, Partition, Knapsack}
\begin{itemize}
\item \problem{3-dim.\ Matching (3-DM)}: drei gleich große Mengen und eine Liste
von Tripeln (je ein Element aus jeder Menge). Wähle Tripel, die jedes Element
\emph{genau einmal} treffen.
\item \problem{3-Exact Cover (3-EC)}: eine Familie 3-elementiger Teilmengen
eines Universums. Wähle einige, die das Universum \emph{exakt} überdecken
(disjunkt, lückenlos).
\item \problem{SubSet Sum}: ganze Zahlen $c_1,\dots,c_n$ und ein Ziel $K$. Gibt
es eine Teilmenge mit Summe \emph{genau} $K$?
\item \problem{Partition}: gibt es eine Teilmenge, die \emph{genau die Hälfte}
der Gesamtsumme trägt?
\item \problem{Knapsack (Rucksack)}: Gegenstände mit Gewicht und Profit,
Kapazität $B$, Zielprofit $P$. Gibt es eine Auswahl mit Gewicht $\le B$ und
Profit $\ge P$?
\end{itemize}
\end{defn}

\begin{bsp}{SubSet Sum ausprobiert}
Zahlen $3, 7, 8, 4$ und Ziel $K = 15$. Probieren: $3+4+8 = 15$ -- ja, die
Teilmenge $\{3,4,8\}$ trifft das Ziel. Das Zertifikat ist genau diese
Teilmenge.
\end{bsp}

\begin{zert}
Für alle diese Probleme ist das Zertifikat die getroffene \emph{Auswahl}
(Tripelmenge, Mengenauswahl, Teilmenge). Der Verifizierer rechnet die geforderte
Summe bzw.\ Überdeckung nach und vergleicht mit den Schranken -- alles in $O(n)$
bis $O(n^2)$. Also liegen alle in $\NP$.
\end{zert}

% ------------------------------------------------------------------
\subsection{Scheduling: $P\|\Cmax$}
% ------------------------------------------------------------------

\begin{defn}{$P\|\Cmax$ (Scheduling auf identischen Maschinen)}
Gegeben $n$ Jobs mit Laufzeiten $p_1,\dots,p_n$ und $m$ gleiche Maschinen.
Verteile die Jobs auf die Maschinen so, dass die \emph{höchste} Maschinenlast --
der \emph{Makespan} $\Cmax$ -- möglichst klein wird.
\end{defn}

\begin{zert}
\textbf{Zertifikat:} die Zuordnung \glqq welcher Job auf welche Maschine\grqq.
\textbf{Verifizierer:} summiere pro Maschine die Laufzeiten, nimm das Maximum,
vergleiche mit der Schranke -- $O(n)$. Also liegt (die Entscheidungsvariante
von) $P\|\Cmax$ in $\NP$.
\end{zert}

\begin{abruf}
\textbf{A11.} Führe den NP-Dreischritt für \problem{Hamiltonkreis} aus:
Zertifikat, Prüfung, Laufzeit.\\
\textbf{A12.} Erkläre das Dualitätsdreieck: Wie hängen \problem{Clique},
\problem{IS} und \problem{VC} zusammen, und über welchen Graphen?
\end{abruf}

% ##################################################################
\section{Reduktionen im Detail}\label{sec:redu}
% ##################################################################

\begin{ziel}
Jetzt zeichnen wir die Pfeile der Landkarte nach. Für jede Reduktion sehen wir:
das Ziel, die Konstruktion Schritt für Schritt, ein Bild oder Zahlenbeispiel und
-- besonders wichtig -- \emph{beide} Richtungen der Korrektheit. Nimm dir für
jede Reduktion Zeit; hier entsteht das eigentliche Verständnis.
\end{ziel}

Jede Reduktion beweist \glqq $X \redp Y$\grqq, also \glqq $Y$ ist mindestens so
schwer wie das bekannte $X$\grqq. Der Aufbau ist immer gleich: Wir bauen aus
einer $X$-Instanz eine $Y$-Instanz und zeigen, dass die Ja/Nein-Antwort dieselbe
bleibt. \glqq Beide Richtungen\grqq{} heißt: Ja-Instanz von $X$ wird zu
Ja-Instanz von $Y$ ($\Rightarrow$), \emph{und} umgekehrt ($\Leftarrow$).

% ------------------------------------------------------------------
\subsection{$\problem{SAT} \redp \problem{Clique}$: aus Logik wird ein Graph}
% ------------------------------------------------------------------

\textbf{Ziel.} Zeige, dass \problem{Clique} mindestens so schwer wie
\problem{SAT} ist, indem du aus einer Formel einen Graphen baust.

\textbf{Die Konstruktion.} Sei $F = F_1 \wedge \dots \wedge F_m$ eine
KNF-Formel.
\begin{itemize}
\item \emph{Ein Knoten pro Literalvorkommen.} Für das $j$-te Literal in Klausel
$i$ setze einen Knoten $[i,j]$.
\item \emph{Kanten nur zwischen \glqq verträglichen\grqq{} Literalen.} Verbinde
$[i,j]$ und $[i',j']$ genau dann, wenn sie in \emph{verschiedenen} Klauseln
liegen ($i \ne i'$) \emph{und} sich nicht widersprechen (nicht $x$ gegen
$\neg x$).
\item \emph{Gesuchte Cliquengröße} $k = m$ (die Zahl der Klauseln).
\end{itemize}
Diese Konstruktion ist offensichtlich in Polynomialzeit machbar.

\begin{intuition}
Warum $k = m$? Eine $m$-Clique muss aus \emph{jeder} Klausel genau einen Knoten
nehmen -- denn Knoten derselben Klausel sind nie verbunden, es passt also höchstens
einer pro Klausel hinein. Und weil sich verbundene Knoten nicht widersprechen,
wählt die Clique aus jeder Klausel ein Literal, ohne sich zu widersprechen. Das
ist \emph{genau} eine erfüllende Belegung.
\end{intuition}

\begin{bsp}{Die Konstruktion an einem Beispiel}
$F = (x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge (x_1 \vee
\neg x_2 \vee \neg x_3)$, also $m = 3$ und $k = 3$. Es entstehen acht Knoten in
drei Spalten (eine je Klausel). Fett eingezeichnet ist die Lösungs-Clique
$\{[1,1],[2,2],[3,1]\}$, die für $x_1,\ \neg x_2,\ x_1$ steht.
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(10,3.6)(-0.7,-0.4)
% Spalte 1
\put(1.0,3.3){\small Klausel 1}
\put(0.5,2.6){\circle*{0.17}}\put(-0.7,2.55){\small $[1,1]\,x_1$}
\put(0.5,1.5){\circle{0.17}}\put(-0.05,1.42){\small $x_2$}
\put(0.5,0.5){\circle{0.17}}\put(-0.05,0.42){\small $x_3$}
% Spalte 2
\put(4.0,3.3){\small Klausel 2}
\put(4.5,2.6){\circle{0.17}}\put(4.7,2.55){\small $\neg x_1$}
\put(4.5,1.5){\circle*{0.17}}\put(4.7,1.42){\small $[2,2]\,\neg x_2$}
% Spalte 3
\put(7.6,3.3){\small Klausel 3}
\put(8.5,2.6){\circle*{0.17}}\put(7.15,2.55){\small $x_1\,[3,1]$}
\put(8.5,1.5){\circle{0.17}}\put(8.7,1.42){\small $\neg x_2$}
\put(8.5,0.5){\circle{0.17}}\put(8.7,0.42){\small $\neg x_3$}
% Clique-Kanten fett
\linethickness{1.3pt}
\put(0.5,2.6){\line(4,-1){4}}   % [1,1]-[2,2]
\put(4.5,1.5){\line(4,1){4}}    % [2,2]-[3,1]
\put(0.5,2.6){\line(1,0){8}}    % [1,1]-[3,1]
\end{picture}
\end{center}
Die drei fetten Kanten bilden ein Dreieck -- die 3-Clique. (Die vielen dünnen
Kanten zwischen anderen verträglichen Paaren sind der Übersicht halber
weggelassen.)
\end{bsp}

\textbf{Korrektheit, beide Richtungen.}
\begin{itemize}
\item[$\Rightarrow$] Ist $F$ erfüllbar, wähle in jeder Klausel ein wahres
Literal. Die zugehörigen Knoten liegen in verschiedenen Klauseln und
widersprechen sich nicht (alle sind ja wahr) -- sie bilden eine $m$-Clique.
\item[$\Leftarrow$] Hat der Graph eine $m$-Clique, so enthält sie aus jeder
Klausel genau einen Knoten, und keine zwei widersprechen sich. Setze die
zugehörigen Literale auf wahr -- das ist widerspruchsfrei und erfüllt jede
Klausel, also $F$.
\end{itemize}

% ------------------------------------------------------------------
\subsection{$\problem{Clique} \redp \problem{VC}$: das Komplement genügt}
% ------------------------------------------------------------------

\textbf{Ziel.} \problem{Vertex Cover} ist mindestens so schwer wie
\problem{Clique}. Und diesmal brauchen wir gar kein Gadget -- das
Dualitätsdreieck erledigt alles.

\textbf{Die Konstruktion.} Aus der \problem{Clique}-Instanz $(G, k)$ mit $n$
Knoten mache die \problem{VC}-Instanz $(\bar G,\ n - k)$: nimm den
\emph{Komplementgraphen} und ersetze die Schranke $k$ durch $n - k$. In
$O(n^2)$ berechenbar.

\begin{intuition}
Woher kommt das $n - k$? Aus dem Dualitätsdreieck. Eine Clique der Größe $k$ in
$G$ ist ein Independent Set der Größe $k$ in $\bar G$. Und das Gegenstück eines
Independent Set ist ein Vertex Cover: Ist $C$ ein Independent Set, so berührt
$V \setminus C$ jede Kante. Aus einem IS der Größe $k$ wird also ein VC der
Größe $n - k$.
\end{intuition}

\textbf{Korrektheit.}
\begin{itemize}
\item[$\Rightarrow$] Hat $G$ eine Clique $C$ mit $|C| \ge k$, so ist $C$ ein
Independent Set in $\bar G$, und $V \setminus C$ ein Vertex Cover in $\bar G$
mit $|V \setminus C| \le n - k$.
\item[$\Leftarrow$] Hat $\bar G$ ein Vertex Cover $D$ mit $|D| \le n - k$, so
ist $V \setminus D$ ein Independent Set in $\bar G$ mit $\ge k$ Knoten -- also
eine Clique der Größe $\ge k$ in $G$.
\end{itemize}

% ------------------------------------------------------------------
\subsection{$\problem{VC} \redp \problem{FVS}$: ungerichtet wird gerichtet}
% ------------------------------------------------------------------

\problem{Feedback Vertex Set (FVS)} fragt: Kann man aus einem \emph{gerichteten}
Graphen $\le k$ Knoten entfernen, sodass \emph{kein gerichteter Kreis} mehr
übrig bleibt?

\textbf{Die Konstruktion.} Aus der \problem{VC}-Instanz $(G, k)$ mache jeden
ungerichteten Kante $\{u,v\}$ zu \emph{zwei antiparallelen Bögen} $u \to v$ und
$v \to u$ -- also einem kleinen Kreis der Länge 2. Schranke bleibt $k$.

\begin{bsp}{Eine Kante wird zu einem 2-Kreis}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(9,1.8)(0,-0.4)
% links: ungerichtet
\put(0.6,0.5){\circle*{0.14}}\put(0.3,0.7){\small $u$}
\put(2.6,0.5){\circle*{0.14}}\put(2.75,0.7){\small $v$}
\put(0.6,0.5){\line(1,0){2}}
\put(1.2,-0.05){\small ungerichtet}
% Pfeil dazwischen
\put(3.3,0.5){\small $\leadsto$}
% rechts: zwei Boegen
\put(5.0,0.5){\circle*{0.14}}\put(4.7,0.7){\small $u$}
\put(7.0,0.5){\circle*{0.14}}\put(7.15,0.7){\small $v$}
\put(5.15,0.68){\vector(1,0){1.7}}   % u->v oben
\put(6.85,0.32){\vector(-1,0){1.7}}  % v->u unten
\put(5.2,-0.05){\small zwei antiparallele Bögen}
\end{picture}
\end{center}
\end{bsp}

\begin{intuition}
Der 2-Kreis $u \to v \to u$ existiert genau wegen dieser einen Kante. Um ihn zu
zerstören, muss man $u$ \emph{oder} $v$ entfernen -- also die Kante
\glqq überdecken\grqq. Kreise kaputtmachen (FVS) und Kanten überdecken (VC) wird
so dasselbe.
\end{intuition}

\textbf{Korrektheit.}
\begin{itemize}
\item[$\Rightarrow$] Ist $C$ ein Vertex Cover mit $|C| \le k$, so berührt $C$
jede Kante -- also enthält $C$ von jedem 2-Kreis einen Knoten. Entfernt man $C$,
verschwindet jeder 2-Kreis. Da alle Kreise im konstruierten Graphen aus solchen
Kanten bestehen, ist er danach kreisfrei.
\item[$\Leftarrow$] Ist $X$ ein FVS mit $|X| \le k$, so muss $X$ jeden 2-Kreis
treffen -- also jede ursprüngliche Kante überdecken. Damit ist $X$ ein Vertex
Cover.
\end{itemize}

% ------------------------------------------------------------------
\subsection{$\problem{3-SAT} \redp \problem{3-Color}$: Wahrheit als Farbe}
% ------------------------------------------------------------------

Diese Reduktion ist raffinierter, deshalb nur die tragende Idee -- die reicht
fürs Verständnis.

\textbf{Die Idee.} Man benutzt drei Farben und tauft sie \textsf{Wahr},
\textsf{Falsch} und \textsf{Neutral}. Für jede Variable $x_i$ baut man ein
kleines \emph{Gadget} aus den Knoten $x_i$ und $\neg x_i$, die miteinander und
mit einem gemeinsamen \textsf{Neutral}-Knoten verbunden sind. Dieses Dreieck
erzwingt, dass $x_i$ und $\neg x_i$ die beiden übrigen Farben bekommen -- eine
wird \textsf{Wahr}, die andere \textsf{Falsch}. So kodiert die Färbung eine
Belegung.

\begin{bsp}{Das Variablen-Gadget}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(4.5,2.4)(-0.3,-0.3)
\put(0,0){\circle*{0.16}}\put(-0.9,-0.05){\small $x_i$}
\put(2,0){\circle*{0.16}}\put(2.15,-0.05){\small $\neg x_i$}
\put(1,1.6){\circle*{0.16}}\put(1.15,1.6){\small \textsf{Neutral}}
\put(0,0){\line(1,0){2}}
\qbezier(0,0)(0.5,0.8)(1,1.6)
\qbezier(2,0)(1.5,0.8)(1,1.6)
\end{picture}
\end{center}
Das Dreieck braucht alle drei Farben. Der \textsf{Neutral}-Knoten nimmt die
neutrale Farbe -- also müssen $x_i$ und $\neg x_i$ \textsf{Wahr} und
\textsf{Falsch} tragen, in irgendeiner Reihenfolge. Genau das ist \glqq die
Variable ist wahr oder falsch, aber nicht beides\grqq.
\end{bsp}

Für jede \emph{Klausel} baut man ein weiteres Gadget, das genau dann korrekt
gefärbt werden kann, wenn mindestens eines ihrer Literale die Farbe \textsf{Wahr}
trägt. Zusammengesetzt gilt: Die Formel ist erfüllbar $\iff$ der Graph ist
3-färbbar.

% ------------------------------------------------------------------
\subsection{$\problem{3-EC} \redp \problem{SubSet Sum}$: Mengen werden Zahlen}
% ------------------------------------------------------------------

Das ist die eleganteste Reduktion des Kurses. Sie verwandelt eine
Mengen-Überdeckung in eine reine Zahlen-Addition.

\textbf{Die Idee.} Schreibe jede 3-elementige Menge als \emph{Bitvektor} über
dem Universum (eine 1 an jeder Stelle, die die Menge enthält). Lies diesen
Bitvektor dann als \emph{Zahl zur Basis $n+1$}, wobei $n$ die Anzahl der Mengen
ist. Das Ziel $K$ ist die Zahl zum Bitvektor \glqq überall 1\grqq.

\begin{intuition}
Warum die krumme Basis $n+1$ statt einfach Basis 2? Damit beim Addieren
\emph{kein Übertrag} entsteht. Es gibt nur $n$ Mengen, also an jeder Stelle
höchstens $n$ Einsen -- das bleibt unter $n+1$, die Stelle \glqq läuft nie
über\grqq. Ohne Übertrag zählt jede Stelle für sich, und \glqq Summe trifft
genau das Ziel\grqq{} bedeutet \glqq jede Stelle genau einmal überdeckt\grqq{} --
also eine exakte Überdeckung. Bei Basis 2 gäbe es Überträge, und falsche
Überdeckungen könnten die Zielsumme zufällig treffen.
\end{intuition}

\begin{bsp}{Komplett durchgerechnet}
Universum $U = \{1,2,3,4,5,6\}$ (also $3m$ mit $m = 2$). Mengen ($n = 4$):
$S_1 = \{1,2,3\}$, $S_2 = \{4,5,6\}$, $S_3 = \{1,2,4\}$, $S_4 = \{3,5,6\}$.
Basis $n+1 = 5$; Stelle für Element $i$ ist $5^{\,i-1}$.
\begin{center}\small
\begin{tabular}{lll}
\toprule
Menge & Bitvektor ($u_1\dots u_6$) & Zahl zur Basis 5\\
\midrule
$S_1=\{1,2,3\}$ & $111000$ & $5^0+5^1+5^2 = 31$\\
$S_2=\{4,5,6\}$ & $000111$ & $5^3+5^4+5^5 = 3875$\\
$S_3=\{1,2,4\}$ & $110100$ & $5^0+5^1+5^3 = 131$\\
$S_4=\{3,5,6\}$ & $001011$ & $5^2+5^4+5^5 = 3775$\\
\midrule
Ziel $K$ & $111111$ & $5^0+\dots+5^5 = 3906$\\
\bottomrule
\end{tabular}
\end{center}
Rechne nach: $S_1 + S_2 = 31 + 3875 = 3906 = K$. Und tatsächlich ist
$\{S_1, S_2\}$ eine exakte Überdeckung von $U$. (Ebenso
$S_3 + S_4 = 131 + 3775 = 3906$, und $\{S_3, S_4\}$ überdeckt $U$ ebenfalls
exakt.) Jede Auswahl, deren Zahlen sich zu $3906$ addieren, trifft jede Stelle
genau einmal -- eine exakte Überdeckung.
\end{bsp}

% ------------------------------------------------------------------
\subsection{$\problem{SubSet Sum} \redp \problem{Partition}$: zwei Zusatzzahlen}
% ------------------------------------------------------------------

\textbf{Ziel.} \problem{Partition} (Teilmenge mit halber Gesamtsumme) ist
mindestens so schwer wie \problem{SubSet Sum}.

\textbf{Die Konstruktion.} Aus den Zahlen $c_1,\dots,c_n$ mit Ziel $K$ und
$N = (\sum_j c_j) + 1$ bilde eine neue Zahlenmenge: alle $c_j$ \emph{plus} zwei
Zusatzzahlen $c_{n+1} = N - K$ und $c_{n+2} = K + 1$.

\begin{intuition}
Die Gesamtsumme der neuen Menge ist $\sum c_j + (N-K) + (K+1) = \sum c_j + N + 1
= 2N$. Die Hälfte ist also $N$. Der Clou: Die beiden Zusatzzahlen summieren sich
zu $(N-K)+(K+1) = N+1$ -- das ist schon \emph{mehr} als eine Hälfte. Sie können
also niemals \emph{beide} in derselben Hälfte liegen; sie werden immer getrennt.
\end{intuition}

\begin{bsp}{Mit echten Zahlen}
Zahlen $3, 5, 8, 4$ (Summe $20$), Ziel $K = 12$. Dann $N = 21$, die
Zusatzzahlen sind $N - K = 9$ und $K + 1 = 13$. Neue Menge:
$\{3, 5, 8, 4, 9, 13\}$ mit Gesamtsumme $42$, Hälfte $21$.\\[0.3em]
Die Original-Teilmenge $\{8, 4\}$ trifft $K = 12$. Ergänzt um die Zusatzzahl $9$
ergibt $\{8, 4, 9\}$ die Summe $21$ -- eine gültige Halbierung. Umgekehrt: Jede
Halbierung enthält genau eine der beiden Zusatzzahlen; zieht man sie ab, bleibt
eine Original-Teilmenge, die $K$ trifft.
\end{bsp}

\textbf{Korrektheit.}
\begin{itemize}
\item[$\Rightarrow$] Trifft eine Teilmenge $S$ der Originalzahlen den Wert $K$,
so hat $S \cup \{N-K\}$ die Summe $K + (N-K) = N$ -- eine Halbierung.
\item[$\Leftarrow$] Jede Halbierung enthält genau eine Zusatzzahl. Enthält sie
$N-K$, so tragen die Originalzahlen darin $N - (N-K) = K$ bei -- eine
Teilmenge mit Summe $K$.
\end{itemize}

\begin{abruf}
\textbf{A13.} Erkläre, warum bei $\problem{3-EC} \redp \problem{SubSet Sum}$ die
Basis $n+1$ (und nicht Basis 2) gewählt wird.\\
\textbf{A14.} Bei $\problem{SubSet Sum} \redp \problem{Partition}$: Warum können
die beiden Zusatzzahlen nie in derselben Hälfte landen?\\
\textbf{A15.} Rechne die $\Rightarrow$-Richtung von $\problem{Clique} \redp
\problem{VC}$ an einem selbst gewählten kleinen Graphen nach.
\end{abruf}

% ##################################################################
\section{Wie schwer \emph{genau}? Die ETH}
% ##################################################################

\begin{ziel}
NP-Vollständigkeit sagt nur \glqq vermutlich nicht polynomiell\grqq. Sie sagt
nicht, \emph{wie} exponentiell. Die Exponentialzeit-Hypothese (ETH) ist eine
schärfere Annahme, aus der man konkrete untere Laufzeitschranken herleitet. Wir
sehen auch, wie so ein Schranken-Beweis wirklich aussieht.
\end{ziel}

\subsection{Die Lücke, die NP-Vollständigkeit offen lässt}

NP-Vollständigkeit ist ein grobes Sieb. Sie wirft ein Problem, das $2^n$
braucht, in denselben Topf wie eines, das nur $2^{\sqrt n}$ braucht -- beide
heißen schlicht \glqq nicht polynomiell\grqq. Für viele Fragen will man aber
genauer wissen: Geht es wenigstens \emph{subexponentiell}, also spürbar besser
als $2^n$?

\begin{defn}{Klein-o und \glqq subexponentiell\grqq}
$f(n) = o(g(n))$ heißt: $f$ wächst \emph{echt langsamer} als $g$, formal
$f(n)/g(n) \to 0$. Achtung: $\delta n$ ist \emph{nicht} $o(n)$ für ein festes
$\delta > 0$. Ein \glqq $2^{o(n)}$-Algorithmus\grqq{} hat einen Exponenten, der
langsamer als linear wächst -- er läuft \emph{subexponentiell}, z.\,B. mit
$2^{\sqrt n}$.
\end{defn}

Das Bild zeigt die drei Welten nebeneinander: harmlos polynomiell,
subexponentiell (die mittlere Kurve), und echt exponentiell.

\begin{bsp}{Drei Wachstumsklassen}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(10,4.6)(-0.7,-0.6)
\put(0,0){\vector(1,0){9.2}} \put(8.9,-0.5){\small $n$}
\put(0,0){\vector(0,1){4.2}} \put(-0.6,4.0){\small Zeit}
\qbezier(0,0)(5,0.5)(9,1.5) \put(8.5,1.4){\small poly}
\qbezier(0,0)(4,0.7)(7.2,4.0) \put(6.6,4.0){\small $2^{o(n)}$}
\qbezier(0,0)(2.5,0.5)(3.3,4.1) \put(2.9,4.15){\small $2^{n}$}
\end{picture}
\end{center}
Die ETH behauptet: Für \problem{3-SAT} gibt es \emph{keinen} Algorithmus der
mittleren (subexponentiellen) Sorte -- es bleibt echt exponentiell.
\end{bsp}

\subsection{Die Hypothese}

\begin{defn}{Exponentialzeit-Hypothese (ETH)}
Es gibt eine Konstante $\delta > 0$, sodass \problem{3-SAT} mit $n$ Variablen
\emph{nicht} in Zeit $2^{\delta n} \cdot \poly$ lösbar ist. Kurz: es gibt
\emph{keinen} $2^{o(n)}$-Algorithmus für \problem{3-SAT}.
\end{defn}

Das ist eine \emph{Annahme} -- stärker als $\Pclass \ne \NP$, aber breit
geglaubt, weil alle bekannten 3-SAT-Algorithmen $c^n$ brauchen. Aus ihr leitet
man untere Schranken für viele andere Probleme ab.

\subsection{Wie ein ETH-Schranken-Beweis aussieht}

Das Beweismuster ist immer \emph{Kontraposition entlang einer Reduktion}: Man
nimmt an, das Zielproblem hätte einen zu schnellen Algorithmus, und leitet
daraus einen zu schnellen Algorithmus für \problem{3-SAT} ab -- Widerspruch zur
ETH.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(13,1.6)(0,-0.3)
\put(0,0.2){\framebox(4.4,1.0){\shortstack{\small \emph{Annahme:} $2^{o(\cdot)}$-Alg.\\ \small für Zielproblem $Y$}}}
\put(4.4,0.7){\vector(1,0){1.7}} \put(4.5,0.85){\small Reduktion}
\put(6.1,0.2){\framebox(3.5,1.0){\shortstack{\small \emph{ergibt:} $2^{o(m)}$-Alg.\\ \small für \problem{3-SAT}}}}
\put(9.6,0.7){\vector(1,0){1.3}}
\put(10.9,0.2){\framebox(2.0,1.0){\shortstack{\small Widerspruch\\ \small zur ETH}}}
\end{picture}
\end{center}

Das Entscheidende -- und der Grund, warum viele hier scheitern -- ist die
\emph{Größenrechnung} im mittleren Pfeil. Machen wir sie einmal konkret.

\begin{idee}{Konkret: die Schranke für \problem{3-Color}}
Es gibt eine Reduktion $\problem{3-SAT} \redp \problem{3-Color}$, die aus einer
Formel mit $n$ Variablen und $m$ Klauseln einen Graphen mit \emph{$O(n+m)$
Knoten} baut. Nimm nun an, jemand könnte \problem{3-Color} in $2^{o(N)}$ lösen,
wobei $N$ die Knotenzahl ist. Setze die Reduktion davor:
\[
\underbrace{2^{o(N)}}_{\text{Annahme}} \text{ mit } N = O(n+m)
\quad\Longrightarrow\quad
\problem{3-SAT} \text{ in } 2^{o(n+m)}.
\]
Nun ist $n + m$ höchstens $O(m)$ (jede Variable kommt in einer Klausel vor, also
$n \le 3m$). Damit hätten wir einen $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
Das ist verboten -- \emph{sofern} wir auch $2^{o(m)}$ ausschließen dürfen. Genau
dafür brauchen wir den nächsten Satz.
\end{idee}

\subsection{Warum das Sparsification-Lemma nötig ist}

\begin{satz}{Sparsification-Lemma}
Unter der ETH gibt es auch \emph{keinen} $2^{o(m)}$-Algorithmus für
\problem{3-SAT}, wobei $m$ die \emph{Klauselzahl} ist.
\end{satz}

\begin{intuition}
Beachte den feinen Unterschied: Die ETH selbst spricht über die
\emph{Variablenzahl} $n$. Die Größenrechnung oben landete aber bei einer
Schranke in der \emph{Klauselzahl} $m$. Und $m$ kann viel größer als $n$ sein
(bis $\sim n^3$). Deshalb folgt \glqq kein $2^{o(m)}$\grqq{} \emph{nicht} direkt
aus \glqq kein $2^{o(n)}$\grqq. Das Sparsification-Lemma füllt genau diese
Lücke: Es überträgt die Härte von $n$ auf $m$. Erst mit ihm schließt sich der
Widerspruch im Bild oben.
\end{intuition}

\begin{stolper}
Immer wenn die Größe deiner konstruierten Instanz an der \emph{Klauselzahl} $m$
hängt (und das ist fast immer so), musst du das Sparsification-Lemma zitieren.
Es ist der am häufigsten vergessene Schritt in ETH-Beweisen.
\end{stolper}

Mit demselben Muster bekommt man unter der ETH untere Schranken $2^{o(n)}$ auch
für \problem{Clique}, \problem{Vertex Cover}, \problem{Independent Set},
\problem{SubSet Sum} und \problem{Partition} -- jeweils mit der passenden
Größenrechnung.

\begin{abruf}
\textbf{A16.} Wenn die ETH \emph{falsch} ist -- folgt daraus $\Pclass = \NP$?
Begründe.\\
\textbf{A17.} Skizziere die Größenrechnung für die \problem{3-Color}-Schranke.
An welcher Stelle kommt das Sparsification-Lemma ins Spiel?
\end{abruf}

% ##################################################################
\section{Damit leben: gute Näherungen}\label{sec:approx}
% ##################################################################

\begin{ziel}
Wenn ein Optimierungsproblem (vermutlich) keine schnelle exakte Lösung hat,
berechnet man in Polynomialzeit eine \emph{beweisbar gute} Näherung. Wir lernen,
was \glqq beweisbar gut\grqq{} heißt, und sehen die wichtigsten Algorithmen --
den TSP-Algorithmus zeichnen wir Schritt für Schritt.
\end{ziel}

\subsection{Was heißt \glqq gute Näherung\grqq?}

\begin{defn}{Multiplikative Güte}
Sei $\OPT(I)$ der optimale Wert einer Instanz $I$. Ein Algorithmus $A$ hat
\emph{Güte $\alpha$}, wenn für \emph{alle} Instanzen gilt:
\begin{itemize}
\item bei Minimierung (TSP, Scheduling): $A(I) \le \alpha \cdot \OPT(I)$ --
die Lösung ist höchstens $\alpha$-mal so teuer wie das Optimum;
\item bei Maximierung (Knapsack): $\OPT(I) \le \alpha \cdot A(I)$ -- die Lösung
liefert mindestens ein $\alpha$-tel des Optimums.
\end{itemize}
Die Güte heißt \emph{scharf}, wenn es Instanzen gibt, die den Faktor (fast)
erreichen -- sie ist dann nicht zu pessimistisch.
\end{defn}

\begin{intuition}
Güte $\alpha$ ist eine \emph{Garantie für den schlimmsten Fall}. Güte 2 bei
einem Minimierungsproblem heißt: Egal welche Eingabe, meine Lösung ist nie mehr
als doppelt so teuer wie die bestmögliche. Kleineres $\alpha$ ist besser;
$\alpha = 1$ wäre exakt optimal.
\end{intuition}

Manche Probleme erlauben sogar eine einstellbare Genauigkeit -- eine ganze
Familie von Algorithmen, bei der du $\alpha = 1 + \varepsilon$ so nah an 1
wählst, wie du willst.

\begin{defn}{PTAS, EPTAS, FPTAS}
Eine Familie $(A_\varepsilon)$ mit Güte $1 + \varepsilon$ für jedes
$\varepsilon > 0$ heißt:
\begin{itemize}
\item \emph{PTAS}, wenn die Laufzeit für jedes feste $\varepsilon$ polynomiell
in $n$ ist ($\varepsilon$ darf im Exponenten stecken, z.\,B. $n^{1/\varepsilon}$);
\item \emph{EPTAS}, wenn die Laufzeit $f(1/\varepsilon) \cdot \poly(n)$ ist --
$\varepsilon$ ist aus dem Exponenten von $n$ heraus;
\item \emph{FPTAS}, wenn die Laufzeit polynomiell in $n$ \emph{und} $1/\varepsilon$
ist -- die stärkste Form.
\end{itemize}
Ein Wort noch: \emph{pseudopolynomiell} heißt eine Laufzeit, die polynomiell in
den \emph{Zahlenwerten} der Eingabe ist -- was wegen des Stolpersteins aus
Kapitel 2 \emph{nicht} dasselbe ist wie polynomiell in der Eingabelänge.
\end{defn}

\subsection{TSP ist im Allgemeinen gar nicht approximierbar}

\begin{satz}{Kein Näherungsalgorithmus für allgemeines TSP}
Für beliebige Distanzen gibt es \emph{keinen} Näherungsalgorithmus mit
beschränkter Güte -- außer $\Pclass = \NP$.\\[0.3em]
\emph{Die Beweisidee:} Man reduziert \problem{Hamiltonkreis}. Echte Kanten
bekommen Distanz 1, fehlende Kanten eine \emph{riesige} Distanz. Gäbe es einen
Algorithmus mit fester Güte $\alpha$, müsste er die billige Hamilton-Tour (Länge
$|V|$) von jeder teuren Tour unterscheiden -- und könnte damit \problem{HK}
exakt entscheiden. Das ist NP-schwer.
\end{satz}

Der Ausweg ist eine realistische Zusatzannahme: das \emph{metrische} TSP. Die
Distanzen sind symmetrisch und erfüllen die \emph{Dreiecksungleichung}
$d(i,j) \le d(i,k) + d(k,j)$ -- ein Umweg ist nie kürzer als der direkte Weg.
Echte Entfernungen erfüllen das immer. Und hier funktioniert ein schöner
Algorithmus.

\subsection{$\Delta$TSP$_1$: der Algorithmus als Bilderfolge}

\begin{idee}{Der Dreisprung}
$\Delta$TSP$_1$ baut zuerst ein billiges Gerüst, das alle Städte verbindet (einen
\emph{minimalen Spannbaum}), macht daraus einen Rundweg über alle Kanten
(\emph{Eulerkreis}, indem alle Knotengrade gerade werden) und kürzt diesen zur
Tour ab. Wir gehen es an einem festen Beispiel durch -- vier Bilder, ein
Algorithmus.
\end{idee}

\noindent Unser Beispiel: die Städte $A,B,C,D,E$ mit $d(A,E)=1$, $d(B,C)=1$,
$d(A,C)=2$, $d(C,D)=2$ (die übrigen Distanzen sind 2 oder 3). Das Layout der
fünf Städte bleibt in allen Bildern gleich.

\medskip
\noindent\textbf{Bild 1 -- die optimale Tour (zum Vergleich).} So sieht die
beste mögliche Rundreise aus. Sie hat Länge~8. Der Algorithmus kennt sie nicht;
wir zeigen sie nur, um am Ende zu vergleichen.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.45){\small $C$}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}
\qbezier(2.6,1.3)(1.55,0.8)(0.5,0.3)  % C-B
\qbezier(0.5,0.3)(2.55,0.5)(4.6,1.3)  % B-D
\qbezier(4.6,1.3)(3.6,2.15)(2.6,3.0)  % D-E
\qbezier(2.6,3.0)(1.55,2.6)(0.5,2.2)  % E-A
\qbezier(0.5,2.2)(1.55,1.75)(2.6,1.3) % A-C
\put(-0.2,-0.2){\small Tour $[C,B,D,E,A,C]$, Länge $8 = \OPT$}
\end{picture}
\end{center}

\medskip
\noindent\textbf{Bild 2 -- Schritt 1: minimaler Spannbaum.} Der Algorithmus
verbindet alle Städte so billig wie möglich zu einem Baum (keine Kreise). Das
sind die Kanten $A$--$E$, $B$--$C$, $A$--$C$, $C$--$D$ mit Gesamtgewicht~6.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.45){\small $C$}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}
\linethickness{1.3pt}
\qbezier(0.5,2.2)(1.55,2.6)(2.6,3.0)  % A-E
\put(1.3,2.75){\small $1$}
\qbezier(0.5,0.3)(1.55,0.8)(2.6,1.3)  % B-C
\put(1.3,0.55){\small $1$}
\qbezier(0.5,2.2)(1.55,1.75)(2.6,1.3) % A-C
\put(1.35,1.95){\small $2$}
\put(2.6,1.3){\line(1,0){2.0}}         % C-D
\put(3.5,1.4){\small $2$}
\put(0.0,-0.2){\small Spannbaum, Gewicht $w(T)=6$}
\end{picture}
\end{center}

\begin{intuition}
Warum ein Spannbaum? Weil er \emph{garantiert billiger} ist als die optimale
Tour: Nimm die optimale Tour und lösche eine ihrer Kanten -- übrig bleibt ein
Weg durch alle Städte, also ein (spezieller) Spannbaum. Der \emph{minimale}
Spannbaum ist höchstens so teuer wie dieser. Also $w(T) \le \OPT$. Das ist der
Kern der Güte-Garantie.
\end{intuition}

\medskip
\noindent\textbf{Bild 3 -- Schritt 2 und 3: verdoppeln, dann Eulerkreis.} Jetzt
verdoppelt der Algorithmus jede Baumkante (im Bild als \glqq $\times 2$\grqq).
Dadurch hat \emph{jeder} Knoten geraden Grad -- die Bedingung für einen
Eulerkreis, einen Rundweg, der jede Kante genau einmal nutzt. Sein Gewicht ist
$2 \cdot 6 = 12$.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.45){\small $C$}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}
\linethickness{1.3pt}
\qbezier(0.5,2.2)(1.55,2.6)(2.6,3.0)
\put(1.25,2.75){\small $\times 2$}
\qbezier(0.5,0.3)(1.55,0.8)(2.6,1.3)
\put(1.25,0.5){\small $\times 2$}
\qbezier(0.5,2.2)(1.55,1.75)(2.6,1.3)
\put(1.3,1.9){\small $\times 2$}
\put(2.6,1.3){\line(1,0){2.0}}
\put(3.4,1.4){\small $\times 2$}
\put(-0.2,-0.2){\small Multigraph, Gewicht $12$, alle Grade gerade}
\end{picture}
\end{center}

\noindent Ein Eulerkreis in diesem Multigraphen ist z.\,B.
$[C, A, E, A, C, B, C, D, C]$ -- er benutzt jede der verdoppelten Kanten einmal
und hat Länge~12. Beachte: Manche Städte (hier $A$, $C$) werden dabei
\emph{mehrfach} besucht.

\medskip
\noindent\textbf{Bild 4 -- Schritt 4: abkürzen zur Tour.} Eine echte Rundreise
darf jede Stadt nur einmal besuchen. Also läuft man den Eulerkreis ab und
\emph{überspringt} bereits besuchte Städte. Aus $[C,A,E,A,C,B,C,D,C]$ wird so
die Tour $[C,A,E,B,D,C]$.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.45){\small $C$}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}
\linethickness{1.1pt}
\qbezier(2.6,1.3)(1.55,1.75)(0.5,2.2)  % C-A
\qbezier(0.5,2.2)(1.55,2.6)(2.6,3.0)   % A-E
\qbezier(2.6,3.0)(1.55,1.65)(0.5,0.3)  % E-B
\qbezier(0.5,0.3)(2.55,0.5)(4.6,1.3)   % B-D
\put(2.6,1.3){\line(1,0){2.0}}          % D-C
\put(-0.2,-0.2){\small Tour $[C,A,E,B,D,C]$, Länge $10 \le 2\cdot\OPT$}
\end{picture}
\end{center}

\begin{intuition}
Warum ist Abkürzen nie schädlich? Weil eine Abkürzung zwei Kanten durch eine
direkte Kante ersetzt, und die \emph{Dreiecksungleichung} garantiert, dass der
direkte Weg nicht länger ist. Deshalb bleibt die Tour $\le 12 = 2 w(T) \le 2
\OPT$. Hier: Länge 10, garantiert $\le 16$, tatsächlich nah an $\OPT = 8$.
\end{intuition}

\subsection{Christofides: schlauer verdoppeln}

$\Delta$TSP$_1$ verdoppelt \emph{alle} Kanten -- das kostet zusätzlich etwa
$w(T) \approx \OPT$, daher die Güte 2. Christofides bemerkt: Wir müssen gar nicht
alle Grade reparieren, sondern nur die \emph{ungeraden}. Und die repariert man
viel billiger.

\begin{idee}{Nur die schiefen Knoten reparieren}
Ein Eulerkreis braucht nur, dass \emph{jeder} Knoten geraden Grad hat. Im
Spannbaum haben aber ohnehin nur \emph{manche} Knoten ungeraden Grad. Statt
alles zu verdoppeln, verbindet Christofides genau diese ungeraden Knoten durch
ein \emph{minimales perfektes Matching} -- die billigste Art, sie paarweise zu
verkuppeln. Das kostet höchstens $\OPT/2$, und daraus folgt Güte $1{,}5$.
\end{idee}

\noindent\textbf{Bild 1 -- der Spannbaum (wie zuvor).} Wir starten mit demselben
minimalen Spannbaum wie bei $\Delta$TSP$_1$.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.45){\small $C$}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}
\linethickness{1.3pt}
\qbezier(0.5,2.2)(1.55,2.6)(2.6,3.0)
\qbezier(0.5,0.3)(1.55,0.8)(2.6,1.3)
\qbezier(0.5,2.2)(1.55,1.75)(2.6,1.3)
\put(2.6,1.3){\line(1,0){2.0}}
\put(0.0,-0.2){\small Spannbaum $T$, Gewicht 6}
\end{picture}
\end{center}

\noindent\textbf{Bild 2 -- die ungeraden Knoten finden.} Wir zählen die Grade im
Baum: $A$ hat Grad 2 (gerade), alle anderen ungerade. Die ungeraden Knoten
$X = \{B, C, D, E\}$ sind mit einem Ring markiert.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}\put(0.5,0.3){\circle{0.34}}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.5){\small $C$}\put(2.6,1.3){\circle{0.34}}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}\put(4.6,1.3){\circle{0.34}}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}\put(2.6,3.0){\circle{0.34}}
\linethickness{1.3pt}
\qbezier(0.5,2.2)(1.55,2.6)(2.6,3.0)
\qbezier(0.5,0.3)(1.55,0.8)(2.6,1.3)
\qbezier(0.5,2.2)(1.55,1.75)(2.6,1.3)
\put(2.6,1.3){\line(1,0){2.0}}
\put(-0.3,-0.2){\small ungerade Grade: $X=\{B,C,D,E\}$ (markiert)}
\end{picture}
\end{center}

\noindent\textbf{Bild 3 -- das Matching hinzufügen.} Unter den möglichen
Paarungen der vier Knoten ist $\{B\text{--}C,\ D\text{--}E\}$ die billigste
(Kosten $1 + 2 = 3$). Diese zwei Matching-Kanten (dünn) kommen zum Baum dazu.
Jetzt haben \emph{alle} Knoten geraden Grad.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.5){\small $C$}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}
\linethickness{1.3pt}
\qbezier(0.5,2.2)(1.55,2.6)(2.6,3.0)
\qbezier(0.5,0.3)(1.55,0.8)(2.6,1.3)
\qbezier(0.5,2.2)(1.55,1.75)(2.6,1.3)
\put(2.6,1.3){\line(1,0){2.0}}
% Matching-Kanten duenn: B-C (schon da -> zweite, versetzt) und D-E
\linethickness{0.4pt}
\qbezier(0.6,0.25)(1.65,0.72)(2.7,1.22)   % zweites B-C (Matching), leicht versetzt
\qbezier(4.6,1.3)(3.6,2.15)(2.6,3.0)       % D-E (Matching)
\put(3.7,2.2){\small $M$}
\put(1.7,0.35){\small $M$}
\put(-0.3,-0.2){\small $+$ Matching $\{B\text{--}C, D\text{--}E\}$, Kosten 3}
\end{picture}
\end{center}

\noindent\textbf{Bild 4 -- Eulerkreis und abkürzen.} Aus $T + M$ gewinnt man
einen Eulerkreis und kürzt ihn ab. Ergebnis: die Tour $[C,B,A,E,D,C]$ mit
Länge~\textbf{9} -- besser als die 10 von $\Delta$TSP$_1$.

\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(5.2,3.4)(-0.3,-0.3)
\put(0.5,2.2){\circle*{0.14}}\put(0.05,2.25){\small $A$}
\put(0.5,0.3){\circle*{0.14}}\put(0.05,0.15){\small $B$}
\put(2.6,1.3){\circle*{0.14}}\put(2.35,1.5){\small $C$}
\put(4.6,1.3){\circle*{0.14}}\put(4.75,1.3){\small $D$}
\put(2.6,3.0){\circle*{0.14}}\put(2.75,3.0){\small $E$}
\linethickness{1.1pt}
\qbezier(2.6,1.3)(1.55,0.8)(0.5,0.3)   % C-B
\put(0.5,0.3){\line(0,1){1.9}}          % B-A
\qbezier(0.5,2.2)(1.55,2.6)(2.6,3.0)   % A-E
\qbezier(2.6,3.0)(3.6,2.15)(4.6,1.3)   % E-D
\put(4.6,1.3){\line(-1,0){2.0}}         % D-C
\put(0.1,-0.2){\small Tour $[C,B,A,E,D,C]$, Länge $9 \le 1{,}5\cdot\OPT$}
\end{picture}
\end{center}

\begin{stolper}
Zwei Dinge werden bei Christofides oft falsch gemacht: Das Matching wird
\emph{nur} über die ungerad-gradigen Knoten des Spannbaums gebildet, nicht über
alle. Und ohne die Dreiecksungleichung bricht wieder das Abkürzen zusammen.
\end{stolper}

\subsection{Knapsack: warum pure Gier scheitert}

Der Rucksack als Optimierungsproblem: Pack Gegenstände mit maximalem
Gesamtprofit ein, ohne die Kapazität $B$ zu überschreiten.

\begin{idee}{Greedy -- und sein Versagen}
Der naheliegende Weg (\emph{Greedy}): sortiere nach \glqq Profit pro Gewicht\grqq{}
und pack der Reihe nach ein, was noch passt. Das ist oft gut, hat aber
\emph{keine} Garantie.
\end{idee}

\begin{bsp}{Greedy kann beliebig schlecht sein}
Zwei Gegenstände: einer mit Gewicht 1 und Profit 1, ein anderer mit Gewicht $B$
und Profit $B-1$. Die Kapazität ist $B$. Greedy schaut auf die Dichte: der
kleine hat Dichte 1, der große Dichte $(B-1)/B < 1$. Also nimmt Greedy den
kleinen -- Profit \textbf{1}. Optimal wäre der große -- Profit $B-1$. Das
Verhältnis $B-1$ wächst mit $B$ ins Unendliche. Keine feste Güte.
\end{bsp}

\begin{idee}{Die Reparatur: Modified Greedy (MGA), Güte 2}
Rechne zwei Kandidaten aus -- das Greedy-Ergebnis \emph{und} \glqq nimm nur den
einen profitabelsten Gegenstand\grqq{} -- und gib den besseren aus. Warum das
reicht: Greedy verliert seinen Profit immer nur an dem \emph{einen}
\glqq Split-Item\grqq, das gerade nicht mehr passte. Dessen Profit fängt der
Einzel-Gegenstand ab. Damit ist man nie schlechter als halb so gut wie das
Optimum. Noch näher kommen der \emph{Sahni}-Algorithmus (probiert alle kleinen
Vorauswahlen, ein PTAS) und das \emph{FPTAS} (rundet die Profite und löst exakt
per dynamischer Programmierung, Güte $1+\varepsilon$).
\end{idee}

\subsection{Scheduling: einfache Regeln, sichtbar im Gantt-Bild}

Zurück zu $P\|\Cmax$: $n$ Jobs auf $m$ Maschinen, minimiere die höchste Last.

\begin{defn}{List Scheduling und LPT}
\emph{List Scheduling:} Gehe die Jobs der Reihe nach durch und lege jeden auf die
\emph{momentan am wenigsten belastete} Maschine. \emph{LPT} (Longest Processing
Time): Sortiere die Jobs zuerst \emph{absteigend}, wende dann List Scheduling an.
\end{defn}

Das folgende Gantt-Bild macht sichtbar, warum die Reihenfolge zählt. Drei Jobs
der Größen $1, 1, 2$ auf zwei Maschinen. Die Balkenlänge ist die Zeit.

\begin{bsp}{List Scheduling gegen LPT}
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(9,4.2)(-1.6,-0.5)
% Zeitachse
\put(0,-0.1){\vector(1,0){4.2}} \put(3.9,-0.5){\small Zeit}
\multiput(0,-0.18)(1,0){4}{\line(0,1){0.12}}
\put(-0.05,-0.5){\small 0}\put(0.95,-0.5){\small 1}\put(1.95,-0.5){\small 2}\put(2.95,-0.5){\small 3}
% List Scheduling
\put(-1.6,3.2){\small \textbf{List Scheduling} (Reihenfolge $1,1,2$):}
\put(-1.3,2.4){\small $M_1$}
\put(0,2.2){\framebox(1,0.6){\small $1$}}
\put(1,2.2){\framebox(2,0.6){\small $2$}}
\put(-1.3,1.5){\small $M_2$}
\put(0,1.3){\framebox(1,0.6){\small $1$}}
\put(3.3,2.3){\small Makespan $3$}
% LPT
\put(-1.6,0.85){\small \textbf{LPT} (sortiert $2,1,1$):}
\put(-1.3,0.3){\small $M_1$}
\put(0,0.1){\framebox(2,0.6){\small $2$}}
\put(-1.3,-0.0){\small }
\put(2.3,0.2){\small Makespan $2$}
\end{picture}
\end{center}
Links stapelt List Scheduling die große $2$ auf eine schon belegte Maschine --
Makespan 3. Rechts legt LPT die große $2$ zuerst, die zwei Einsen wandern auf
$M_2$ -- Makespan 2, das Optimum.
\end{bsp}

\begin{satz}{Die Güten -- und die Idee dahinter}
List Scheduling hat Güte $2 - \tfrac1m$, LPT die bessere Güte
$\tfrac43 - \tfrac1{3m}$ -- beide scharf.\\[0.3em]
\emph{Die Idee (List Scheduling):} Betrachte die Maschine mit der höchsten Last
und den \emph{letzten} Job $J_k$, der auf ihr landete. In dem Moment, als $J_k$
zugewiesen wurde, war diese Maschine die \emph{leerste} -- also waren \emph{alle}
Maschinen mindestens so voll wie $L - p_k$. Mit den zwei Universalschranken
$\OPT \ge \frac1m \sum p_i$ (die Gesamtlast verteilt sich auf $m$ Maschinen) und
$\OPT \ge p_{\max}$ (der größte Job muss irgendwo laufen) folgt die Schranke.
\end{satz}

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

\begin{idee}{Zwei Belegungen genügen}
Beim Optimierungsproblem MAX-3-SAT will man \emph{möglichst viele} Klauseln
erfüllen. Erstaunlich einfacher Algorithmus mit Güte 2: Werte die Formel nur
\emph{zweimal} aus -- einmal mit \glqq alle Variablen falsch\grqq{} ($\beta_0$),
einmal mit \glqq alle wahr\grqq{} ($\beta_1$) -- und nimm die bessere.\\[0.3em]
Warum das reicht: Jede Klausel enthält mindestens ein Literal, entweder ein
positives oder ein negatives. Ein positives Literal wird von $\beta_1$ erfüllt,
ein negatives von $\beta_0$. Also erfüllt \emph{jede} Klausel mindestens eine
der beiden Belegungen. Damit erfüllen $\beta_0$ und $\beta_1$ zusammen $\ge m$
Klauseln, die bessere von beiden also $\ge m/2$. Da $\OPT \le m$, ist das
mindestens $\OPT/2$.
\end{idee}

\begin{abruf}
\textbf{A18.} Nenne die vier Schritte von $\Delta$TSP$_1$ und sage bei jedem,
warum er die Güte-2-Schranke stützt.\\
\textbf{A19.} Warum ist Christofides besser als $\Delta$TSP$_1$, obwohl beide
mit demselben Spannbaum starten?\\
\textbf{A20.} Warum genügt beim Greedy-Rucksack der zusätzliche Vergleich mit
dem \glqq besten Einzel-Gegenstand\grqq, um von \glqq unbeschränkt schlecht\grqq{}
auf Güte 2 zu kommen?
\end{abruf}

% ##################################################################
\section{Jenseits von NP: das Halteproblem}\label{sec:halt}
% ##################################################################

\begin{ziel}
Ein kurzer Blick über den Rand. Wir treffen ein Problem, das NP-schwer ist, aber
\emph{nicht} in $\NP$ liegt -- weil es überhaupt nicht lösbar ist. Das zeigt,
dass \glqq schwer\grqq{} und \glqq in NP\grqq{} wirklich zwei verschiedene
Dinge sind.
\end{ziel}

\begin{defn}{Halteproblem}
Gegeben die Beschreibung eines Programms $M$ und einer Eingabe $w$: Hält $M$ auf
$w$ irgendwann an, oder läuft es für immer?
\end{defn}

Das Halteproblem ist \emph{unentscheidbar} -- kein Algorithmus löst es, mit
keiner noch so großen Laufzeit. Das ist ein tiefes, bewiesenes Resultat (Turing).
Und trotzdem ist es NP-schwer.

\begin{aha}
Man reduziert \problem{SAT} darauf. Zu einer Formel $\varphi$ baut man ein
Programm $M_\varphi$, das \emph{alle} Belegungen der Reihe nach durchprobiert und
genau dann anhält, wenn es eine erfüllende findet. Dann gilt: $\varphi$ erfüllbar
$\iff$ $M_\varphi$ hält. Der Clou liegt im Zeitverhalten: $M_\varphi$ läuft im
Nein-Fall \emph{ewig} -- aber die \emph{Konstruktion} von $M_\varphi$ aus
$\varphi$ ist billig (polynomiell), und nur darauf kommt es bei einer Reduktion
an. Also ist das Halteproblem mindestens so schwer wie \problem{SAT}. In $\NP$
liegt es aber nicht -- es ist ja nicht einmal entscheidbar.
\textbf{NP-schwer ist nicht dasselbe wie NP-vollständig.}
\end{aha}

% ##################################################################
\section{Das große Ganze}
% ##################################################################

\begin{ziel}
Wir ziehen die Fäden zusammen: eine Übersicht der ganzen Reise und ein
Wahr/Falsch-Test zur Selbstkontrolle.
\end{ziel}

\subsection{Die Reise auf einen Blick}

\begin{center}\small
\begin{tabular}{p{3.4cm}p{10.2cm}}
\toprule
Station & Kernidee \\
\midrule
$\Pclass$ & effizient \emph{lösbar} (polynomielle Laufzeit)\\
$\NP$ & effizient \emph{überprüfbar} (Zertifikat prüfen bzw.\ raten)\\
$\Pclass \subseteq \NP$ & Lösen ist mindestens so schwer wie Prüfen; Gleichheit offen\\
$A \redp B$ & \glqq $B$ mindestens so schwer wie $A$\grqq; Richtung: bekannt $\redp$ neu\\
NP-vollständig & die schwersten in $\NP$; \problem{SAT} ist der Anker (Cook--Levin)\\
Vererbungskorollar & neues Problem schwer zeigen: eine Reduktion \emph{plus} Nachweis $\in\NP$\\
ETH & schärfer als NP-Vollständigkeit: konkrete $2^{o(\cdot)}$-Schranken\\
Approximation & für schwere Optimierung: beweisbar gute Näherung mit Gütegarantie\\
\bottomrule
\end{tabular}
\end{center}

\subsection{Wahr oder falsch? (Die Begründung zählt)}

Wenn du das Fundament verstanden hast, kannst du jede dieser Aussagen begründen.

\begin{center}\small
\begin{tabular}{p{7.2cm}cp{4.9cm}}
\toprule
Aussage & W/F & Begründung \\
\midrule
Löst eine ratende Maschine ein Problem in Polyzeit, dann auch eine gewöhnliche. &
F$^{*}$ & Das wäre $\Pclass=\NP$ -- unbekannt. \\
\addlinespace
$A$ NP-schwer $\Rightarrow A \in \NP$. & F & Halteproblem: NP-schwer, nicht
einmal lösbar. \\
\addlinespace
$L \in \NP$ und $L \redp \problem{3-SAT}$ $\Rightarrow$ $L$ NP-vollständig. &
F & Falsche Richtung -- \emph{auf} 3-SAT reduzieren zeigt keine Schwere. \\
\addlinespace
$\problem{3-SAT} \redp L$ und $L \redp \problem{3-SAT}$ $\Rightarrow$ $L$
NP-vollständig. & W & Erstes gibt Schwere, zweites gibt $L \in \NP$. \\
\addlinespace
ETH falsch $\Rightarrow \Pclass = \NP$. & F & $2^{o(n)}$ kann superpolynomiell
bleiben. \\
\bottomrule
\end{tabular}
\end{center}
{\footnotesize $^{*}$ nicht als wahr beweisbar; äquivalent zu $\Pclass=\NP$.}

\begin{aha}
Du hast jetzt das \emph{Warum} beisammen: was ein Problem schwer macht, wie
Schwere von einem Problem zum anderen fließt, wo die Grenzen liegen, und was man
tut, wenn exakte Lösungen zu teuer sind. Das ist das Fundament des ganzen
Kurses.
\end{aha}

\noindent\textbf{Der nächste Schritt.} Dieses Heft hat dir das Verständnis
gegeben (Schritt 1 und 2 deines Lernmodells). Jetzt kommt die Anwendung
(Schritt 3 und 4): Nimm die Präsenz-, Haus- und Klausuraufgaben und führe dort
selbst aus, was hier als Idee stand -- Reduktionen \emph{vollständig} beweisen
(beide Richtungen!), Güte-Schranken herleiten, Worst-Case-Instanzen bauen. Viel
Erfolg.

% ##################################################################
\appendix
\renewcommand{\thesection}{\Alph{section}}
\section{Lösungen zu den Abruf-Fragen}\label{sec:loesungen}
% ##################################################################

Erst selbst beantwortet, dann hier vergleichen -- nur so wirkt das aktive
Abrufen.

\loes{A1.} Ein konstanter Faktor wie 1000 ($\approx 2^{10}$) verschiebt die
exponentielle Kurve nur um eine \emph{additive} Konstante: Du schaffst rund 20
Knoten mehr -- ein einziges Mal. Danach wächst das Problem exponentiell weiter,
die Hardware bleibt gleich. Exponentielles Wachstum lässt sich nicht durch
schnellere Hardware einholen.

\loes{A2.} \glqq Kennen keinen\grqq{} = niemand hat bisher einen Algorithmus
gefunden (eine Wissenslücke). \glqq Gibt keinen\grqq{} = die Nichtexistenz ist
bewiesen. Für die Clique gilt nur das Erste; ein Nichtexistenzbeweis fehlt (die
Frage $\Pclass$ vs.\ $\NP$ ist offen).

\loes{A3.} Ja. $n^4$ ist polynomiell (fester Exponent $d=4$), also liegt das
Problem in $\Pclass$ und gilt im Sinne der Theorie als effizient.

\loes{A4.} Bis $K$ zu zählen kostet $K$ Schritte. Aber $K$ ist als Eingabe nur
$O(\log K)$ Zeichen lang, sein \emph{Wert} ist exponentiell in dieser Länge. Die
Laufzeit ist also exponentiell in der Eingabegröße.

\loes{A5.} \textbf{Zertifikat:} eine Knotenmenge $C$. \textbf{Verifizierer:}
prüfe, ob jede Kante mindestens einen Endpunkt in $C$ hat ($O(|E|)$), und ob
$|C| \le k$. \textbf{Korrektheit:} Gibt es ein Vertex Cover der Größe $\le k$,
wird es akzeptiert; sonst keines. \textbf{Laufzeit} polynomiell. (Rate-Sicht:
$C$ raten, dann prüfen.)

\loes{A6.} Der Verifizierer bekommt das Zertifikat \emph{geschenkt} und muss es
nur prüfen. Der Löser hat niemanden, der ihm die Lösung vorlegt -- er muss sie
selbst finden, und dafür können exponentiell viele Kandidaten in Frage kommen.
Prüfen beginnt einen Schritt weiter als Lösen.

\loes{A7.} $\problem{Clique} \redp \problem{Vertex Cover}$ -- vom bekannt
schweren \problem{Clique} auf das neue \problem{VC}. So erbt \problem{VC} die
Schwere. Die Gegenrichtung würde über \problem{VC} nichts aussagen (sie zeigte
nur \glqq höchstens so schwer wie das schwere Clique\grqq).

\loes{A8.} $A \redp B$ bedeutet: $B$ ist \emph{mindestens so schwer} wie $A$.

\loes{A9.} (1) eine Reduktion von einem bekannten NP-vollständigen Problem
\emph{auf} das neue; (2) der Nachweis, dass das neue Problem in $\NP$ liegt.
Vergessen wird am häufigsten (2) -- ohne ihn hat man nur NP-\emph{Schwere}, nicht
Vollständigkeit.

\loes{A10.} \problem{SubSet Sum} ist NP-vollständig. Läge \emph{ein}
NP-vollständiges Problem in $\Pclass$, könnte man jedes $L \in \NP$ über
$L \redp \problem{SubSet Sum}$ effizient lösen -- also $\Pclass = \NP$.

\loes{A11.} \textbf{Zertifikat:} die Besuchsreihenfolge (Permutation der Knoten).
\textbf{Verifizierer:} prüfe, ob jeder Knoten genau einmal vorkommt und jede
aufeinanderfolgende sowie die schließende Kante existiert -- $O(|V|+|E|)$.
(Rate-Sicht: Reihenfolge raten, dann prüfen.)

\loes{A12.} Für eine Knotenmenge $C$ gilt: $C$ ist Clique in $G$ $\iff$ $C$ ist
Independent Set im Komplementgraphen $\bar G$ $\iff$ $V \setminus C$ ist Vertex
Cover in $\bar G$. Die drei Probleme sind dasselbe, betrachtet über den
Komplementgraphen und die Komplement-Knotenmenge.

\loes{A13.} Bei Basis $n+1$ und höchstens $n$ Summanden entsteht an keiner Stelle
ein Übertrag -- jede Ziffer zählt für sich. Dann bedeutet \glqq Summe trifft das
Ziel\grqq{} genau \glqq jede Stelle wird genau einmal überdeckt\grqq. Bei Basis 2
gäbe es Überträge, und eine falsche Auswahl könnte das Ziel zufällig treffen.

\loes{A14.} Die beiden Zusatzzahlen sind $N-K$ und $K+1$; ihre Summe ist $N+1$.
Eine Hälfte hat aber nur den Wert $N$. Zwei Zahlen mit Summe $N+1 > N$ passen
also nie zusammen in dieselbe Hälfte -- sie werden immer getrennt.

\loes{A15.} Beispiel: $G$ mit $V=\{1,2,3,4\}$ und Kanten $\{1,2\},\{2,3\},\{1,3\}$
(ein Dreieck plus isolierter Knoten 4), $n=4$, $k=3$. Clique $C=\{1,2,3\}$. Im
Komplement $\bar G$ (Kanten $\{1,4\},\{2,4\},\{3,4\}$) ist $V \setminus C=\{4\}$
ein Vertex Cover der Größe $n-k = 1$ -- Knoten 4 berührt alle Kanten von $\bar G$.

\loes{A16.} Nein. \glqq ETH falsch\grqq{} heißt nur: \problem{3-SAT} geht in
$2^{o(n)}$ -- das kann immer noch superpolynomiell sein, z.\,B.\ $2^{\sqrt n}$.
Umgekehrt gilt aber: $\Pclass = \NP$ würde die ETH sofort widerlegen.

\loes{A17.} Die Reduktion $\problem{3-SAT} \redp \problem{3-Color}$ baut aus $n$
Variablen und $m$ Klauseln einen Graphen mit $O(n+m)$ Knoten. Ein
$2^{o(N)}$-Algorithmus für \problem{3-Color} ($N$ = Knotenzahl) ergäbe damit
einen $2^{o(n+m)}$-Algorithmus für \problem{3-SAT}, und wegen $n+m = O(m)$ einen
$2^{o(m)}$-Algorithmus. Genau hier kommt das \emph{Sparsification-Lemma} ins
Spiel: Es verbietet $2^{o(m)}$ für \problem{3-SAT} -- der Widerspruch ist
komplett.

\loes{A18.} (1) Minimaler Spannbaum $T$: er ist billiger als die optimale Tour,
$w(T) \le \OPT$. (2) Kanten verdoppeln: Gesamtlänge $2w(T) \le 2\OPT$. (3)
Eulerkreis: nutzt die geraden Grade, ändert die Länge nicht. (4) Abkürzen:
verlängert wegen der Dreiecksungleichung nicht. Zusammen: $d(R) \le 2\OPT$.

\loes{A19.} $\Delta$TSP$_1$ verdoppelt \emph{alle} Baumkanten und zahlt dafür
zusätzlich etwa $w(T) \approx \OPT$ -- Güte 2. Christofides fügt stattdessen nur
ein minimales perfektes Matching auf den ungerad-gradigen Knoten hinzu, das
höchstens $\OPT/2$ kostet. Deshalb landet er bei $w(T) + \OPT/2 \le 1{,}5\,\OPT$.

\loes{A20.} Greedy verliert seinen Profit immer nur an dem einen
\glqq Split-Item\grqq, das gerade nicht mehr in den Rucksack passte. Dessen Profit
ist höchstens der maximale Einzelprofit. Der zweite Kandidat (bester
Einzel-Gegenstand) deckt genau diesen Fall ab. Also ist das Bessere von beiden
mindestens halb so gut wie das Optimum -- Güte 2.

\end{document}