\contentsline {section}{\numberline {1}Ein Problem, das sich wehrt}{3}{section.1}%
\contentsline {subsection}{\numberline {1.1}Freunde auf einer Party}{3}{subsection.1.1}%
\contentsline {subsection}{\numberline {1.2}Der naive Weg -- und warum er explodiert}{3}{subsection.1.2}%
\contentsline {subsection}{\numberline {1.3}Die Frage, um die es geht}{4}{subsection.1.3}%
\contentsline {section}{\numberline {2}Was heißt eigentlich \quotedblbase schnell\textquotedblleft ?}{5}{section.2}%
\contentsline {subsection}{\numberline {2.1}Laufzeit hängt von der Eingabegröße ab}{5}{subsection.2.1}%
\contentsline {subsection}{\numberline {2.2}Polynomiell gegen exponentiell -- die entscheidende Grenze}{5}{subsection.2.2}%
\contentsline {subsection}{\numberline {2.3}Warum wir Probleme als Ja/Nein-Fragen schreiben}{6}{subsection.2.3}%
\contentsline {section}{\numberline {3}Prüfen ist leichter als Lösen}{7}{section.3}%
\contentsline {subsection}{\numberline {3.1}Die Sudoku-Beobachtung}{7}{subsection.3.1}%
\contentsline {subsection}{\numberline {3.2}Zertifikat und Verifizierer}{8}{subsection.3.2}%
\contentsline {subsection}{\numberline {3.3}Die zweite Brille: Raten}{8}{subsection.3.3}%
\contentsline {subsection}{\numberline {3.4}P steckt in NP -- und die Millionenfrage}{9}{subsection.3.4}%
\contentsline {section}{\numberline {4}\quotedblbase Mindestens so schwer wie\textquotedblleft {} -- Reduktionen}{10}{section.4}%
\contentsline {subsection}{\numberline {4.1}Ein Problem mit einem anderen lösen}{10}{subsection.4.1}%
\contentsline {subsection}{\numberline {4.2}Die Richtung -- der Fehler, der alle Punkte kostet}{11}{subsection.4.2}%
\contentsline {subsection}{\numberline {4.3}Reduktionen lassen sich verketten}{11}{subsection.4.3}%
\contentsline {section}{\numberline {5}Die härtesten Probleme}{12}{section.5}%
\contentsline {subsection}{\numberline {5.1}NP-schwer und NP-vollständig}{12}{subsection.5.1}%
\contentsline {subsection}{\numberline {5.2}Warum ein einziger Algorithmus alles verändern würde}{13}{subsection.5.2}%
\contentsline {subsection}{\numberline {5.3}Das erste NP-vollständige Problem: Cook--Levin}{13}{subsection.5.3}%
\contentsline {subsection}{\numberline {5.4}Der Motor: das Vererbungskorollar}{13}{subsection.5.4}%
\contentsline {section}{\numberline {6}Der Problem-Zoo}{14}{section.6}%
\contentsline {subsection}{\numberline {6.1}Die Landkarte: eine Kette ab SAT}{14}{subsection.6.1}%
\contentsline {subsection}{\numberline {6.2}Die Logik-Probleme}{15}{subsection.6.2}%
\contentsline {subsection}{\numberline {6.3}Die Graph-Probleme und ihr Dreieck}{15}{subsection.6.3}%
\contentsline {subsection}{\numberline {6.4}Eine Reduktion ganz durchgerechnet: $\textsc {SAT} \leq _{p}\textsc {$k$-Clique}$}{16}{subsection.6.4}%
\contentsline {subsection}{\numberline {6.5}Die Zahl- und Mengen-Probleme}{17}{subsection.6.5}%
\contentsline {subsection}{\numberline {6.6}Zwei kurze, elegante Reduktionen}{18}{subsection.6.6}%
\contentsline {section}{\numberline {7}Wie schwer \emph {genau}? Die ETH}{18}{section.7}%
\contentsline {subsection}{\numberline {7.1}Die Lücke, die NP-Vollständigkeit lässt}{19}{subsection.7.1}%
\contentsline {subsection}{\numberline {7.2}Die Hypothese und warum man sie braucht}{19}{subsection.7.2}%
\contentsline {section}{\numberline {8}Damit leben: gute Näherungen}{20}{section.8}%
\contentsline {subsection}{\numberline {8.1}Was heißt \quotedblbase gute Näherung\textquotedblleft ?}{20}{subsection.8.1}%
\contentsline {subsection}{\numberline {8.2}TSP: von \quotedblbase unmöglich\textquotedblleft {} zu Güte $1{,}5$}{21}{subsection.8.2}%
\contentsline {subsection}{\numberline {8.3}Knapsack: warum Gier allein scheitert}{23}{subsection.8.3}%
\contentsline {subsection}{\numberline {8.4}Scheduling: einfache Regeln, scharfe Schranken}{23}{subsection.8.4}%
\contentsline {subsection}{\numberline {8.5}MAX-3-SAT: Güte 2 fast geschenkt}{24}{subsection.8.5}%
\contentsline {section}{\numberline {9}Jenseits von NP: das Halteproblem}{25}{section.9}%
\contentsline {section}{\numberline {10}Das große Ganze}{25}{section.10}%
\contentsline {subsection}{\numberline {10.1}Die Reise in einem Bild}{25}{subsection.10.1}%
\contentsline {subsection}{\numberline {10.2}Verständnis-Check: wahr oder falsch?}{25}{subsection.10.2}%
\contentsline {subsection}{\numberline {10.3}Wie es weitergeht}{26}{subsection.10.3}%