Komplexitätstheorie
Die Komplexitätstheorie beschäftigt sich mit der Schwierigkeit von Problemen der Informatik. Sie ermöglicht Aussagen darüber, wie viel Zeit mindestens benötigt wird, um ein Problem zu lösen.
Bei der Bearbeitung der zweiten Runde des Bundeswettbewerbs kommt es oft vor, dass sich für ein Problem kein schneller Algorithmus finden lässt, sondern für alle Lösungen die Laufzeit exponentiell mit der Eingabelänge wächst. Wenn wir zum Beispiel versuchen zu prüfen, ob ein aussagenlogischer Ausdruck erfüllbar ist, ist es kaum zu vermeiden, alle möglichen Variablenbelegungen durchzuprobieren. In solchen Fällen ist es oft möglich zu beweisen, dass es keinen Algorithmus geben kann, der schneller als exponentiell ist.
Komplexitätsklassen
In der Komplexitätstheorie werden Probleme in Schwierigkeitsklassen eingeordnet. Für den Bundeswettbewerb sind vor allem die Klassen , und -HARD wichtig. Zur Klasse gehören Probleme, die in polynomieller Zeit gelößt werden können, das heißt, es gibt einen Algorithmus mit Zeitkomplexität mit Eingabelänge und festem . Die Zugehörigkeit zu dieser Klasse wird durch einen Algorithmus zusammen mit einer Analyse seiner Laufzeit gezeigt. Zur Klasse gehören Probleme, bei denen die Richtigkeit einer Lösung schnell (in polynomieller Zeit) überprüfbar ist. Zugehörigkeit wird auch hier durch Angabe eines Algorithmus gezeigt. Zur Klasse -HARD gehören Probleme, die mindestens so schwer sind, wie alle Probleme in . Für solche Probleme gibt es (vermutlich) keine schnellen Algorithmen.
Die Klasse P
Probleme gehören zur Klasse , wenn es einen Algorithmus gibt, der sie in polynomieller Zeit löst, also Zeit in mit Eingabelänge und festem benötigt. Wir wollen die Klasse an einem Beispiel illustrieren. Es sei die Frage zu beantworten, ob eine Liste von Zahlen irgendeine Zahl mehrmals enthält. Dieses Problem lässt sich mit folgendem Algorithmus lösen:
enthält_duplikate(list : Liste von Int) -> Bool :
initialisiere Liste unique
für alle n in list:
für alle m in unique:
if n == m:
gib Falsch zurück
füge n zu unique hinzu
gib Wahr zurück
Dieser Algorithmus muss im Schritt maximal Vergleichsoperationen durchführen, denn die aktuelle Zahl muss höchstens mit allen vorherigen verglichen werden. Er braucht also Vergleichsoperationen, und unter der Annahme, dass ein Vergleich konstante Zeit benötigt, so auch Zeit . Damit haben wir gezeigt, dass dieses Problem in liegt.
Die Klasse NP
Zur Klasse gehören Probleme, bei denen eine Lösung schnell überprüft werden kann. Die Erfüllbarkeit aussagenlogischer Ausdrücke von oben ist ein Beispiel dafür: Wenn wir eine Variablenbelegung gegeben haben, können wir schnell prüfen, ob diese den Ausdruck erfüllt, in dem wir den Ausdruck mit der Belegung einfach auswerten. Außerdem sind alle Probleme in auch in : Wenn wir für ein Problem in eine Lösung gegebeben haben, können wir den schnellen Lösungsalgorithmus anwenden und überprüfen, ob die gegebene Lösung zur gefundenen equivalent ist, und so schnell deren Richtigkeit prüfen.
Die Klasse NP-HARD
Ein Problem ist in -HARD, wenn es mindestens so schwer ist, wie alle Probleme in , was bedeutet, dass ein schneller Algorithmus für dieses Problem auch alle Probleme in löst. Wir sagen dann auch, dass das Problem -schwer ist. Diese Eigenschaft lässt sich recht außwendig direkt beweisen, in dem man die Begriffe Problem, Lösung und Algorithmus weiter formalisiert und über diese Definitionen argumentiert, dafür siehe Abschnitt Satz von Cook. Sie lässt sich aber auch indirekt beweisen, in dem man auf Probleme zurückgreift, bei denen die Zugehörigkeit zu -HARD schon bewiesen wurde.
Die Zugehörigkeit zu wird -HARD gezeigt, in dem man zeigt, dass ein Problem, welches bekanntermaßen in -HARD ist, leichter oder gleich schwer zu lösen ist. Das wird durch eine sogenannte Reduktion gezeigt. Bei einer Reduktion konstruiert man ein bekanntes Problem in dem zu untersuchenden Problem, so dass ein Lösungsalgorithmus für das neue Problem auch das bekannte Problem lösen kann. Wenn für das neue Problem ein schneller Algorithmus existieren würde (also mit polynomieller Zeit), würde für das alte Problem in -HARD auch ein schneller Algorithmus existieren, was aber der bekannten Schwierigkeit wiederspricht. Es ist dabei wichtig, dass diese Reduktion auch in polynomieller Zeit durchgeführt werden kann, denn nur in diesem Fall lassen sich die Reduktion und der Algorithmus zu einem neuen, schnellen Algorithmus verbinden.
Wir wollen nun zeigen, dass SET-COVERING -schwer ist, in dem wir VERTEX-COVER darauf reduzieren. Eine Instanz des SET-COVERING-Problems besteht aus einer Zahl , einer Menge , dem Universum, und Teilmengen für alle . Es soll geprüft werden, ob es unterschiedliche gibt, so dass deren Vereinigung gleich ist.
Beispielsweise kann unser Universum und , , , und sein. Für ist die Instanz nicht erfüllbar, denn wir können kein auswählen, welches gleich ist. Für ist die Instanz hingegen mit , , und erfüllbar, denn
Beim VERTEX-COVER-Problem ist ein ungerichteter Graph mit Kanten und Knoten , und eine Zahl gegeben. Hier soll geprüft werden, ob es Knoten gibt, so dass die Vereinigung derer angrenzenden Kanten ergibt. Für VERTEX-COVER ist bekannt, dass es -schwer ist.
Wir reduzieren eine Instanz von VERTEX-COVER auf SET-COVERING, in dem wir das Universum auf die Kanten setzen, und für jeden Knoten ein einführen, welches die an dem Knoten endenden Kanten enthält, während gleich bleibt. Wenn wir nun verschiedene auswählen können, so dass deren Vereinigung gleich ist, dann decken die zugehörigen Knoten auch die Kanten des Graphen ab. Da diese Reduktion in polynomieller Zeit durchführbar ist (der Beweis sei dem interessierten Leser als Übung überlassen), ist SET-COVERING somit -Schwer.
Die Klasse NP-COMPLETE
Die Klasse -COMPLETE ist die Schnittmenge von und -Schwer. Für diese Probleme gibt es bis heute auch noch keine schnellen Algorithmen, jedoch kann ein schneller Algorithmus für irgendein -schweres Problem auch diese Probleme schnell lösen.
Weiterführende Literatur
Um eigene Reduktionen durchzuführen, ist es einerseits sinnvoll, sich mit schon vorhandenen Reduktionen zu beschäftigen, zum Beispiel mit Karps 21 -vollständigen Problemen. Algorithmen, eine Einführung von Cormen et al. erläutert auch einige Reduktionen und stellt allgemeine Techniken zur Reduktion vor. Für eine ausführliche formale Einführung in die Komplexitätstheorie siehe zum Beispiel Theoretische Informatik, Eine umfassende Einführung von Priese und Erk.