Eine Grundlegung der Average-Case Komplexittstheorie

Dieses Buch hat die sogenannte average-case Komplexittstheorie zum Gegenstand, ein vergleichsweise junges Gebiet der strukturellen Komplexittstheorie. Die "klassische" strukturelle Komplexittstheorie 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 Stdten mit einer
Entfernungstabelle, man suche die krzeste Route, die einen Handlungsreisenden alle Stdte genau einmal besuchen lt und ihn an seinen Ausgangsort zurckbringt. 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 Lsung findet, bentigt
fr einige "schwie rige" Eingaben eine sehr lange Laufzeit. In der Praxis beobachtet man aber hufig bei derartigen worst-case schwierigen Problemen, da man die tatschlich auftreten den Probleminstanzen in sehr kurzer Zeit
lsen 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 Lsen des Problems aussieht. Man interessiert sich somit dafr, wie aufwendig die Problemlsung im Mittel ist, d. h. zum Beispiel welche mittlere Laufzeit ein optimaler Lsungsalgorithmus hat. Die average-case
Komple xittstheorie beschftigt sich mit der Frage nach dem mittleren Aufwand, der zum Lsen einer Probleminstanz notwendig ist, wenn die Probleminstanzen einer gege benen Verteilung unterliegen.