Komplexitätstheorie

Komplexitätstheorie — ist das eine Disziplin für der Welt entrückte Theoretiker oder ein Kerngebiet der modernen Informatik?

Es ist sicherlich unmöglich, den Begriff „Problem“ abzugrenzen oder gar zu formalisieren. Unter einem „algorithmischen Problem” wollen wir ein Problem verstehen, das für eine Bearbeitung mit Rechnern geeignet ist und für das die Menge korrekter Ergebnisse wohldefiniert ist. Das Problem, ein gerechtes Urteil für einen Angeklagten zu finden, ist schon deshalb nicht algorithmisch, weil es aus rechtsphilosophischen Gründen nicht für die Bearbeitung mit einem Rechner geeignet ist. Dagegen ist das Problem, einen deutschen Text in eine andere Sprache zu übersetzen, für eine Bearbeitung mit Rechnern geeignet, allerdings ist nicht klar abgegrenzt, welche Ergebnisse korrekt sind. Im Sinne der Komplexitätstheorie ist also auch das Übersetzungsproblem kein algorithmisches Problem. Ein Musterbeispiel eines algorithmischen Problems ist die Berechnung eines kürzesten Weges von s nach t in einem Graphen, in dem s und t zu den Knoten gehören und die Kanten mit positiven Kosten (Distanzen oder Reisezeiten) bewertet sind.

Im letzten Kapitel haben wir die Schwierigkeiten diskutiert, die sich bei der Definition der algorithmischen Komplexität von Problemen ergeben. Im allgemeinen Fall gibt es für die minimale asymptotische maximale Rechenzeit nur untere und obere Schranken. Dann liegen die möglichen unteren und oberen Schranken aber so eng beieinander, dass der Unterschied bei der Frage, ob ein Problem effizient lösbar ist, keine Rolle spielt. Wir werden daher in Zukunft bei allen algorithmischen Problemen von ihrer algorithmischen Komplexität sprechen. Wenn diese im oben genannten Sinne nicht definiert ist, benutzen wir bei positiven Aussagen über die effiziente Lösbarkeit des Problems die oberen Schranken und bei negativen Aussagen die unteren Schranken.

Es ist uns mit Hilfe von Reduktionskonzepten wie „<T“ und „<D“ gelungen, die algorithmische Ähnlichkeit einiger Probleme nachzuweisen. Bisher sind wir aber unsystematisch vorgegangen und haben nur den Umgang mit Reduktionskonzepten eingeübt. Nun wollen wir untersuchen, was wir mit weiteren Reduktionen zwischen wichtigen Problemen erreichen können.

Wir haben jetzt das Werkzeug bereitgestellt, um die NP-Vollständigkeit von Entscheidungsproblemen zu beweisen und wollen die zehn in Kapitel 2.2 vorgestellten Problemkreise behandeln. In diesem Kapitel interessieren uns die Grundvarianten der Probleme und einige verwandte Problemstellungen. In Kapitel 7 werden wir dann spezielle Problemvarianten diskutieren und untersuchen, wo die Grenze zwischen schwierigen, also NP-vollständigen, und einfachen, also polynomiell lösbaren Varianten verläuft. Mit den Ergebnissen aus Kapitel 4.2 folgt für die Auswertungs-und Optimierungsvarianten der Entscheidungsprobleme, die wir hier als NP-vollständig nachweisen, dass sie NP-äquivalent sind. Außerdem wissen wir aus Kapitel 5.2, dass alle betrachteten Entscheidungsprobleme in NP enthalten sind. Zum Beweis der NP-Vollständigkeit genügt es jeweils, ein NP-vollständiges Problem auf das betrachtete Problem polynomiell zu reduzieren. Einerseits wollen wir eine große Problemvielfalt betrachten und andererseits wollen wir nicht zu viele Reduktionen ausführlich diskutieren. Daher werden wir nur die Beweise, die neue Ideen enthalten, ausführlich vorstellen und uns bei anderen Beweisen auf die wesentlichen Ideen beschränken.

Für die in Kapitel 2.2 vorgestellten Problemkreise wollen wir exemplarisch untersuchen, wo die Trennlinie zwischen einfachen und schwierigen Varianten verläuft. Dabei vergleichen wir ähnlich aussehende Probleme wie die beiden Überwachungsprobleme VC und EC und wir schränken die Eingabemenge von allgemeinen Problemen wie GC auf verschiedene Weise ein. Behauptungen, dass bestimmte Probleme effizient lösbar sind, werden wir hier nur in Ausnahmefällen beweisen. Derartige Beweise finden sich in Lehrbüchern über effiziente Algorithmen. Wir verzichten auch auf einige NP-Vollständigkeitsbeweise.

Bisher haben wir Optimierung als scharf formuliertes Kriterium verstanden. Nur die Berechnung einer bewiesenermaßen optimalen Lösung zählt als Er­gebnis, alles andere ist ein Misserfolg. Falls wir ein Optimierungsproblem effizient exakt lösen können, sollten wir dies auch tun. Allerdings sind sehr viele wichtige Optimierungsprobleme NP-äquivalent. Wenn wir für derartige Probleme effizient Lösungen berechnen können, deren Wert garantiert na­he am Wert optimaler Lösungen liegt, ist dies ein guter Ausweg aus dem (vermuteten) NP4P-Dilemma. Dies gilt für Probleme aus realen Anwendun­gen, in denen die Parameter auf Schätzungen beruhen, noch mehr, da exakte Optimierung unter diesen Voraussetzungen eine Fiktion ist. Für Entschei­dungsprobleme A bezeichnen wir die zugehörigen Optimierungsprobleme mit MAX-A bzw. MIN-A.

Grundlegende Überlegungen

In Kapitel 3 haben wir die grundlegenden Komplexitätsklassen vorgestellt und untersucht. Die Beziehungen zwischen ihnen wurden in Theorem 3.5.3 zusammengefasst. Reduktionen dienen dazu, Beziehungen zwischen einzelnen Problemen herzustellen. Wenn ein Problem mit einer Komplexitätsklasse C verglichen wird, kann es sich als C-einfach, C-schwierig, C-vollständig oder C-äquivalent erweisen. So lernen wir etwas über die Komplexität von Problemen in Relation zur Komplexität von anderen Problemen und in Relation zu Komplexitätsklassen. Die NPVollständigkeitstheorie hat sich als heutzutage bestes Mittel erwiesen, um unter der NP¡ÙP-Hypothese viele wichtige Probleme als schwierig zu klassifizieren.

In diesem Kapitel werden Komplexitätsklassen auf der Basis interaktiver Beweise definiert. Die Motivation dafür ist nicht offenkundig. Es ergeben sich Komplexitätsklassen mit interessanten Eigenschaften und Beziehungen zu den schon bekannten Komplexitätsklassen. Aber viel wichtiger sind die Ergebnisse, die mit dieser neuen Sicht auf die Komplexität von Problemen erreicht werden können. In Kapitel 11.3 werden wir die schon angekündigten Argumente vorstellen, mit denen wir begründen, warum das Graphenisomorphieproblem als nicht NP-vollständig eingeschätzt wird. In Kapitel 11.4 diskutieren wir interaktive Beweise, die überzeugen, aber den Kern des Beweises nicht offen legen. Derartige Beweise können als Kennwort (password) benutzt werden. Schließlich beruhen das PCP-Theorem (siehe Kapitel 12) und die darauf aufbauende Theorie zur Komplexität von Approximationsproblemen auf der hier eingeführten Sicht, Probleme durch interaktive Beweise zu lösen. Bevor wir den zentralen Begriff eines interaktiven Beweises, der auf Goldwasser, Micali und Rackoff (1989) zurückgeht, in Kapitel 11.2 einführen, wollen wir den Begriff eines Beweises beleuchten.

Interaktive Beweissysteme haben sich in Kapitel 11 als nützliches Werkzeug herausgestellt. Hier werden wir randomisiert verifizierbare Beweise (probabilistically checkable proofs, PCP) untersuchen. Bei geeigneter Einschränkung der Ressourcen erhalten wir eine neue Charakterisierung der Komplexitätsklasse NP. Diese Charakterisierung, das so genannte PCP-Theorem, ist eine mehr als erstaunliche Aussage und ihr Korrektheitsbeweis ist zu komplex, um hier dargestellt zu werden. Wir werden aber in Kapitel 12.2 ein schwächeres Resultat beweisen, um einen Einblick in die Möglichkeiten randomisiert verifizierbarer Beweise zu bekommen Das PCP-Theorem gilt als das wichtigste Ergebnis der Komplexitätstheorie seit dem Theorem von Cook. Die in Kapitel 8 auf der klassischen NP-Vollständigkeitstheorie beruhende Theorie der Komplexität von Approximationsproblemen stößt ja an enge Grenzen. Das PCP-Theorem ermöglicht nun neue Methoden, um die Komplexität von Approximationsproblemen zu untersuchen. In Kapitel 12.3 werden wir exemplarisch Nichtapproximierbarkeitsresultate für MAX-3-SAT und das Cliquen-problem vorstellen und in Kapitel 12.4 die APX-Vollständigkeit von MAX3-SAT beweisen.

Wie schon in der Einleitung betont, liegt der Schwerpunkt dieses Lehrbuchs auf konkreten komplexitätstheoretischen Ergebnissen für wichtige Probleme. Neuere Aspekte wie die Komplexität von Approximationsproblemen oder interaktive Beweissysteme stehen dabei im Vordergrund und strukturelle Aspekte werden auf den Kern reduziert, der für die gewünschten Ergebnisse nötig ist. Daneben gibt es klassische Themen der Komplexitätstheorie mit Ergebnissen von fundamentaler Bedeutung. Von diesen sollen einige in diesem Kapitel dargestellt werden.

Ohne dies bisher thematisiert zu haben, waren unsere Überlegungen auf Softwarelösungen ausgerichtet. Wer einen effizienten Algorithmus für ein Optimierungsproblem wie das TSP oder das Rucksackproblem entwerfen will, denkt an einen Algorithmus, der für eine beliebige Anzahl von Städten oder Objekten arbeitet. Beim Hardwareentwurf ist die Situation anders. Wenn ein Prozessor mit 64-Bit-Zahlen arbeitet, soll ein Dividierer für Zahlen der Bitlänge 64 die ersten 64 Bits des Quotienten berechnen. Das zugehörige Berechnungsmodell ist ein Schaltkreis (circuit). Schaltkreise für Eingabelänge n haben die booleschen Variablen x₁,..., x_n und die booleschen Konstanten 0 und 1 als Eingaben. Sie lassen sich als Folge G1i..., GS von Bausteinen (Gatter, gates) beschreiben. Jeder Baustein Gi hat zwei Eingänge Ei,1 und Ei,2i für die die Eingaben und die früheren Bausteine G1,..., Gz_1 in Frage kommen. Er wendet eine binäre boolesche Operation opi auf seine Eingänge an. Die im Schaltkreis realisierten Funktionen ergeben sich auf natürliche Weise. Die Eingabevariable xi wird auch als Funktion aufgefasst, ebenso eine boolesche Konstante als konstante Funktion. Wenn an den Eingängen von Gi die Funktionen gi,1 und gi,2 realisiert werden, wird von Gi die Funktion realisiert. Anschaulicher ist die Darstellung von Schaltkreisen durch gerichtete azyklische Graphen.

Das Ziel der Komplexitätstheorie besteht darin, die Mindestressourcen zur Lösung von algorithmischen Problemen abzuschätzen. Die bisher bewiesenen unteren Schranken beruhen auf komplexitätstheoretischen Hypothesen oder beziehen sich auf spezielle Szenarien wie das Black-Box-Szenario. In diesem und dem folgenden Kapitel werden ohne komplexitätstheoretische Hypothese untere Schranken für eine Ressource unter der Bedingung, dass eine andere Ressource beschränkt ist, gezeigt, also so genannte Trade-off-Resultate. Dazu gehören in Kapitel 16 untere Schranken für die Größe tiefenbeschränkter Schaltkreise oder für die Größe längenbeschränkter Branchingprogramme. Die wohl frühesten Resultate dieser Art bezogen sich auf die Fläche A und die parallele Rechenzeit T von VLSI-Schaltkreisen (siehe auch Kapitel 15.5). Für bestimmte Funktionen f = (fa) hat Thompson (1979) gezeigt, dass das Produkt aus Fläche und quadrierter Rechenzeit asymptotisch mindestens wie n2 wachsen muss, formal ausgedrückt: AT2 = Q(n2). Also können Fläche und parallele Rechenzeit nicht gleichzeitig sehr klein werden. Yao (1979) hat den Kern der beim Beweis dieser Schranken benutzten Ideen herausgefiltert und von der konkreten Anwendung getrennt. Daraus entstand die Theorie der Kommunikationskomplexität, die auf folgendem Kommunikationsspiel (cornmunication game) beruht.

Wir haben schon mehrfach betont, dass Entscheidungsprobleme oder Sprachen L ⊑{0,1}^* und Familien boolescher Funktionen f = (f_n) mit einer Ausgabe in enger Beziehung stehen. Zu L gehört die Funktionenfamilie f^L = (f^L _n), wobei f^L _n: {0,1}ⁿ→{0,1} für die Eingabe a den Wert 1 genau dann annimmt, wenn a ∈ List. Zu f = (f_n) mit f_n: {0,1}ⁿ →{0, 1} gehört das Entscheidungsproblem L_f, das sich als Vereinigung aller fn^-1(1) beschreiben lässt. Bei der Betrachtung von Familien boolescher Funktionen haben wir jedoch die einzelne Funktion f_n im Blickpunkt. Uns interessieren also nichtuniforme Komplexitätsmaße wie die Größe und Tiefe von Schaltkreisen oder die Größe und Länge von Branchingprogrammen. In Kapitel 14 haben wir die Unterschiede zwischen uniformen und nichtuniformen Komplexitätsmaßen diskutiert und in Kapitel 15 das nichtuniforme Maß der Kommunikationskomplexität untersucht. Hier wollen wir versuchen, untere Schranken für die Komplexität boolescher Funktionen bezüglich der oben genannten Komplexitätsmaße zu beweisen.

Wir haben schon mehrfach betont, dass Entscheidungsprobleme oder Sprachen L ⊑{0,1}^* und Familien boolescher Funktionen f = (f_n) mit einer Ausgabe in enger Beziehung stehen. Zu L gehört die Funktionenfamilie f^L = (f^L _n), wobei f^L _n: {0,1}ⁿ→{0,1} für die Eingabe a den Wert 1 genau dann annimmt, wenn a ∈ List. Zu f = (f_n) mit f_n: {0,1}ⁿ →{0, 1} gehört das Entscheidungsproblem L_f, das sich als Vereinigung aller fn^-1(1) beschreiben lässt. Bei der Betrachtung von Familien boolescher Funktionen haben wir jedoch die einzelne Funktion f_n im Blickpunkt. Uns interessieren also nichtuniforme Komplexitätsmaße wie die Größe und Tiefe von Schaltkreisen oder die Größe und Länge von Branchingprogrammen. In Kapitel 14 haben wir die Unterschiede zwischen uniformen und nichtuniformen Komplexitätsmaßen diskutiert und in Kapitel 15 das nichtuniforme Maß der Kommunikationskomplexität untersucht. Hier wollen wir versuchen, untere Schranken für die Komplexität boolescher Funktionen bezüglich der oben genannten Komplexitätsmaße zu beweisen.