47 lines
5.5 KiB
TeX
47 lines
5.5 KiB
TeX
\relax
|
|
\providecommand\hyper@newdestlabel[2]{}
|
|
\providecommand\HyField@AuxAddToFields[1]{}
|
|
\providecommand\HyField@AuxAddToCoFields[2]{}
|
|
\@writefile{toc}{\contentsline {section}{\numberline {1}Ein Problem, das sich wehrt}{3}{section.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Cliquen in einem Graphen}{3}{subsection.1.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Warum der naive Weg explodiert}{3}{subsection.1.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}Die eigentliche Frage}{4}{subsection.1.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {2}Was heißt \quotedblbase schnell\textquotedblleft ?}{4}{section.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Laufzeit misst man in der Eingabegröße}{5}{subsection.2.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Probleme als Ja/Nein-Fragen}{5}{subsection.2.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {3}Prüfen ist leichter als Lösen}{6}{section.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Die Sudoku-Beobachtung}{6}{subsection.3.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Der NP-Dreischritt -- so zeigt man \quotedblbase $\in \mathsf {NP}$\textquotedblleft }{6}{subsection.3.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}P steckt in NP -- und die Millionenfrage}{7}{subsection.3.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {4}\quotedblbase Mindestens so schwer wie\textquotedblleft {} -- Reduktionen}{7}{section.4}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Ein Problem mit einem anderen lösen}{8}{subsection.4.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Die Richtung -- der teuerste Fehler}{8}{subsection.4.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {5}Die härtesten Probleme: NP-vollständig}{9}{section.5}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Der Anker: Cook--Levin}{10}{subsection.5.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Die Landkarte der Schwere}{10}{subsection.5.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {6}Der Problem-Zoo}{11}{section.6}\protected@file@percent }
|
|
\newlabel{sec:zoo}{{6}{11}{Der Problem-Zoo}{section.6}{}}
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Logik: SAT und 3-SAT}{11}{subsection.6.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Graphen: das Dualitätsdreieck}{12}{subsection.6.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3}Färbung, Hamiltonkreis, TSP}{14}{subsection.6.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {6.4}Mengen und Zahlen}{14}{subsection.6.4}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {6.5}Scheduling: $P\|C_{\max }$}{15}{subsection.6.5}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {7}Wie schwer \emph {genau}? Die ETH}{16}{section.7}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {7.1}Die Lücke, die NP-Vollständigkeit lässt}{16}{subsection.7.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2}Wie man ETH-Schranken beweist}{17}{subsection.7.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {8}Damit leben: gute Näherungen}{17}{section.8}\protected@file@percent }
|
|
\newlabel{sec:approx}{{8}{17}{Damit leben: gute Näherungen}{section.8}{}}
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {8.1}Was heißt \quotedblbase gute Näherung\textquotedblleft ?}{18}{subsection.8.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {8.2}TSP: der Algorithmus Schritt für Schritt}{18}{subsection.8.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {8.3}Knapsack: warum Gier scheitert -- und wie man sie rettet}{19}{subsection.8.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {8.4}Scheduling: Regeln und Gantt-Bild}{19}{subsection.8.4}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {8.5}MAX-3-SAT: Güte 2 mit zwei Belegungen}{20}{subsection.8.5}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {9}Jenseits von NP: das Halteproblem}{21}{section.9}\protected@file@percent }
|
|
\newlabel{sec:halt}{{9}{21}{Jenseits von NP: das Halteproblem}{section.9}{}}
|
|
\@writefile{toc}{\contentsline {section}{\numberline {10}Das große Ganze}{21}{section.10}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {10.1}Die Reise auf einen Blick}{21}{subsection.10.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {10.2}Wahr oder falsch? (Begründung zählt)}{22}{subsection.10.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {A}Lösungen zu den Abruf-Fragen}{22}{appendix.A}\protected@file@percent }
|
|
\newlabel{sec:loesungen}{{A}{22}{Lösungen zu den Abruf-Fragen}{appendix.A}{}}
|
|
\gdef \@abspage@last{23}
|