Dieses Buch hat die sogenannte average-case Komplexitätstheorie zum
Gegenstand, ein vergleichsweise junges Gebiet der strukturellen
Komplexitätstheorie. Die "klassische" strukturelle Komplexitätstheorie
untersucht, wie schwierig ein al- gorithmisches Problem im schwierigsten
Fall (worst-case) ist. Ein solches algorith- misches Problem ist zum
Beispiel das Traveling Salesman Problem: gegeben eine Menge von Städten
mit einer Entfernungstabelle, man suche die kürzeste Route, die einen
Handlungsreisenden alle Städte genau einmal besuchen läßt und ihn an
seinen Ausgangsort zurückbringt. Jede konkrete Entfernungstabelle ist
eine soge- nannte Probleminstanz des obigen, allgemeinen Problems. Vom
Traveling Salesman Problem wird angenommen, daß es im worst-case sehr
schwierig ist, d. h., jeder Algo- rithmus, der zu jeder Probleminstanz
eine Lösung findet, benötigt für einige "schwie- rige" Eingaben eine
sehr lange Laufzeit. In der Praxis beobachtet man aber häufig bei
derartigen worst-case schwierigen Problemen, daß man die tatsächlich
auftreten- den Probleminstanzen in sehr kurzer Zeit lösen kann, daß also
das Auftreten von schwierigen Probleminstanzen sehr unwahrscheinlich
ist. Unterliegt die Eingabe ei- ner Wahrscheinlichkeitsverteilung, so
ist es daher wichtig zu wissen, wie die mittlere Laufzeit eines
Algorithmus zum Lösen des Problems aussieht. Man interessiert sich somit
dafür, wie aufwendig die Problemlösung im Mittel ist, d. h. zum Beispiel
welche mittlere Laufzeit ein optimaler Lösungsalgorithmus hat. Die
average-case Komple- xitätstheorie beschäftigt sich mit der Frage nach
dem mittleren Aufwand, der zum Lösen einer Probleminstanz notwendig ist,
wenn die Probleminstanzen einer gege- benen Verteilung unterliegen.
