Eine Grundlegung der Average-case-Komplexitätstheorie

Viac o knihe

Die klassische Komplexitätstheorie untersucht die Schwierigkeit von Probleminstanzen im schlimmsten Fall. In der Praxis zeigt sich jedoch oft, dass solche Probleme schnell gelöst werden können, was die Wahrscheinlichkeit schwieriger Instanzen in Anwendungen verringert. Daher ist es wichtig, die durchschnittliche Komplexität zu betrachten, insbesondere die mittlere Laufzeit optimaler Lösungsalgorithmen, wenn die Eingaben einer Wahrscheinlichkeitsverteilung folgen. Die average-case Komplexitätstheorie konzentriert sich nicht auf spezifische Probleme oder Verteilungen, sondern auf allgemeine Zusammenhänge, ähnlich der worst-case Komplexitätstheorie. Ein zentrales Thema ist die Frage, ob es auch im Durchschnittsfall Probleme gibt, die NP-vollständig sind. Das Buch entwickelt einen allgemeinen Rahmen für diese Theorie und leitet mehrere grundlegende Ergebnisse innerhalb dieses Rahmens ab. Die Inhalte umfassen eine Einführung, starke und schwache average-case Modelle, Klassen von Dichten und Sprachklassen sowie Aspekte der Komplexitäts- und Vollständigkeitstheorie.