Komplexität und Berechenbarkeit: Halteproblem, Automaten, P und NP

Ein Navigationsgerät soll den kürzesten Weg durch ein Straßennetz finden, ein Stundenplanprogramm Räume und Lehrkräfte verteilen, ein Prüfprogramm entscheiden, ob ein anderes Programm jemals fertig wird. Für die ersten beiden gibt es Verfahren, die schnell genug sind oder es nicht sind. Für das letzte gibt es überhaupt kein Verfahren, und das lässt sich beweisen. Die beiden Fragen „Was ist berechenbar?“ und „Was ist effizient berechenbar?“ sind die Themen dieser Seite.

Du brauchst die Aussagenlogik, die Graphen und die O-Notation von Rekursionen und erzeugende Funktionen.

Was ist berechenbar?

Ein Algorithmus ist eine endliche Vorschrift, die man Schritt für Schritt mechanisch ausführen kann, wie das Verfahren zur schriftlichen Division. Um zu beweisen, dass etwas nicht berechenbar ist, muss man erst genau festlegen, was ein Algorithmus ist. Alan Turing tat das 1936 mit einem Gedankenmodell: Die Turingmaschine hat ein unendliches Band aus Feldern mit Symbolen, einen Lese-Schreib-Kopf und eine endliche Zahl von Zuständen. In jedem Schritt liest sie das Symbol unter dem Kopf, schreibt ein neues, bewegt den Kopf um ein Feld und wechselt den Zustand, alles nach einer festen Tabelle. Alonzo Church kam 1936 mit dem Lambda-Kalkül auf dasselbe Ergebnis. Alle bisher bekannten Berechnungsmodelle, vom Computerprogramm bis zum Zellularautomaten, sind nicht mächtiger. Die Church-Turing-These behauptet, dass Turingmaschinen genau das erfassen, was man intuitiv „berechenbar“ nennt. Sie lässt sich nicht beweisen, weil „intuitiv“ keine mathematische Definition ist, aber nichts spricht gegen sie.

Ein Problem mit Antworten „ja“ oder „nein“ heißt entscheidbar, wenn ein Algorithmus es für jede Eingabe in endlicher Zeit löst. Es heißt semi-entscheidbar, wenn ein Algorithmus bei Ja-Antworten anhält und bei Nein-Antworten vielleicht ewig läuft. Ein Beispiel ist die Frage, ob eine Gleichung eine ganzzahlige Lösung hat: Man probiert alle Zahlen durch und hält an, sobald man eine findet.

Das Halteproblem

Beweis (Diagonalisierung, wie bei Cantor). Angenommen, es gäbe einen solchen Entscheider $H(P,x)$, der „hält“ oder „hält nicht“ liefert. Dann konstruiere ein Programm $D$, das als Eingabe den Text eines Programms $P$ bekommt und so arbeitet: Es ruft $H(P,P)$ auf, also die Frage, ob $P$ bei seinem eigenen Text als Eingabe anhält. Antwortet $H$ „hält“, dann läuft $D$ in eine Endlosschleife. Antwortet $H$ „hält nicht“, dann hält $D$ an. Was passiert nun bei $D(D)$? Hält $D(D)$ an, dann hat $H(D,D)$ „hält“ geantwortet, und nach Konstruktion läuft $D(D)$ endlos: Widerspruch. Hält $D(D)$ nicht an, dann hat $H$ „hält nicht“ geantwortet, und $D(D)$ hält an: wieder ein Widerspruch. Also gibt es $H$ nicht. $\square$

Daraus folgen viele weitere Unmöglichkeitsaussagen. Nach dem Satz von Rice ist jede nichttriviale Aussage über das Verhalten von Programmen unentscheidbar, zum Beispiel „berechnet dieses Programm die Nullfunktion?“. Ein Programm, das alle Fehler in beliebigen Programmen findet, kann es nicht geben. Auch Hilberts zehntes Problem, ob eine diophantische Gleichung ganzzahlige Lösungen hat, ist unentscheidbar: Das bewies Juri Matijassewitsch 1970, auf der Arbeit von Davis, Putnam und Julia Robinson aufbauend (siehe Robinson und Matijassewitsch und Diophantische Gleichungen). Dass die Gültigkeit von Formeln der Prädikatenlogik unentscheidbar ist, zeigten Church und Turing 1936, siehe Prädikatenlogik.

Endliche Automaten

Das einfachste Berechnungsmodell hat nur endlichen Speicher. Ein deterministischer endlicher Automat besteht aus einer endlichen Zustandsmenge $Z$, einem Eingabealphabet $\Sigma$, einer Übergangsfunktion $\delta :Z\times \Sigma \to Z$, einem Startzustand und einer Menge akzeptierender Zustände. Er liest ein Wort Zeichen für Zeichen, wechselt jedes Mal den Zustand und akzeptiert das Wort, wenn er am Ende in einem akzeptierenden Zustand steht. Die Menge der akzeptierten Wörter ist die vom Automaten erkannte Sprache.

Die von endlichen Automaten erkannten Sprachen heißen regulär. Es sind genau die Sprachen, die sich durch reguläre Ausdrücke wie ${(0|1)}^{\ast }1$ beschreiben lassen (Satz von Kleene). Wegen des endlichen Speichers können Automaten nicht beliebig weit zählen. Die Sprache $\{a^n{b}^n:n\ge 0\}$ ist nicht regulär. Beweisidee (Pumping-Lemma): Hätte ein Automat mit $k$ Zuständen diese Sprache erkannt, dann müsste er beim Lesen von $a^k$ einen Zustand zweimal besuchen. Die Schleife dazwischen kann man beliebig oft wiederholen, und das Wort mit einer anderen Zahl von $a$ als $b$ würde ebenfalls akzeptiert. Dafür braucht man Kellerautomaten oder Turingmaschinen. In dieser Reihenfolge wachsen die Fähigkeiten: endliche Automaten, Kellerautomaten (kontextfreie Sprachen wie Klammerausdrücke), Turingmaschinen.

Laufzeit und Komplexität

Bei berechenbaren Problemen kommt es darauf an, wie schnell. Man misst die Rechenschritte als Funktion der Eingabelänge $n$ und vergleicht mit der O-Notation. Der Unterschied zwischen polynomiellem und exponentiellem Wachstum ist drastisch:

Ein Exponentialverfahren ist schon bei $n=100$ aussichtslos, und ein schnellerer Rechner hilft kaum: Verdoppelt sich seine Geschwindigkeit, schafft man bei $2^n$ nur ein Element mehr. Deshalb gilt ein Problem als praktisch lösbar, wenn es einen Algorithmus mit polynomieller Laufzeit gibt.

Die Klassen P und NP

Zu $\mathbf{P}$ gehören das Sortieren, kürzeste Wege in Graphen, die Frage nach einem Euler-Kreis (alle Grade gerade, siehe Graphentheorie) und die Lösung linearer Gleichungssysteme. Zu $\mathbf{NP}$ gehört außerdem alles, wofür man eine Lösung nur raten und dann prüfen muss:

• Teilsummenproblem: Gibt es in $\{3,34,4,12,5,2\}$ eine Teilmenge mit Summe $9$? Das Zertifikat $\{4,5\}$ ist sofort nachgerechnet, ein Auffinden ohne Rat erfordert im schlimmsten Fall $2^n$ Möglichkeiten.
• Hamilton-Kreis: Gibt es einen Rundweg, der jeden Knoten genau einmal besucht? Das Zertifikat ist der Weg.
• Erfüllbarkeit (SAT): Gibt es eine Belegung der Variablen, die eine aussagenlogische Formel wahr macht (siehe Normalformen)? Das Zertifikat ist die Belegung.
• Faktorisieren: Hat $n$ einen Teiler zwischen $2$ und $k$? Das Zertifikat ist der Teiler.

Jedes Problem in $\mathbf{P}$ liegt auch in $\mathbf{NP}$, man ignoriert das Zertifikat und rechnet selbst. Die große Frage ist, ob $\mathbf{P}=\mathbf{NP}$ gilt. Fast alle Fachleute vermuten, dass es nicht so ist, dass also Prüfen leichter ist als Finden. Bewiesen ist es bis heute nicht, und es gilt als eines der wichtigsten offenen Probleme der Mathematik und der Informatik.

NP-Vollständigkeit

Ein Problem $A$ lässt sich auf $B$ reduzieren, wenn man jede Instanz von $A$ in polynomieller Zeit in eine Instanz von $B$ übersetzen kann, sodass die Antworten übereinstimmen. Dann ist $B$ mindestens so schwer wie $A$. Ein Problem in $\mathbf{NP}$ heißt NP-vollständig, wenn sich jedes Problem in $\mathbf{NP}$ darauf reduzieren lässt. Findet jemand für ein einziges NP-vollständiges Problem einen schnellen Algorithmus, folgt $\mathbf{P}=\mathbf{NP}$.

Stephen Cook zeigte das 1971, indem er die Berechnung einer nichtdeterministischen polynomiellen Turingmaschine durch eine aussagenlogische Formel beschrieb. Leonid Levin fand dasselbe Ergebnis unabhängig. Richard Karp wies 1972 in „Reducibility Among Combinatorial Problems“ für 21 weitere Probleme die NP-Vollständigkeit nach, darunter Hamilton-Kreis, Rucksack und Graphfärbung, und machte die Frage $\mathbf{P}$ gegen $\mathbf{NP}$ bekannt. Heute kennt man Tausende NP-vollständige Probleme. Für sie nimmt man in der Praxis Näherungsverfahren, Heuristiken oder Spezialfälle in Kauf.

Ein Beispiel einer Reduktion: Das Problem „Hamilton-Kreis“ lässt sich auf das Problem des Handlungsreisenden reduzieren. Man gibt dem Graphen $G$ die Entfernung $1$ für jede Kante und $2$ für jede Nichtkante in der Vervollständigung zum vollständigen Graphen und fragt, ob es eine Rundreise der Länge $n$ gibt. Sie existiert genau dann, wenn $G$ einen Hamilton-Kreis hat. Daher ist das Handlungsreisenden-Problem mindestens so schwer.

Übungen

Geschichte: von Hilbert zu Cook

David Hilbert stellte 1928 das Entscheidungsproblem: Gibt es ein mechanisches Verfahren, das für jede Formel der Prädikatenlogik entscheidet, ob sie allgemeingültig ist? Kurt Gödel hatte 1931 mit den Unvollständigkeitssätzen die Grenzen der Beweisbarkeit gezeigt. Alan Turing führte 1936 in „On Computable Numbers“ seine Maschine ein und bewies, dass das Entscheidungsproblem keine Lösung hat. Church kam im selben Jahr mit dem Lambda-Kalkül zum gleichen Ergebnis. Danach verlagerte sich die Frage von „ob“ zu „wie schnell“: 1971 zeigte Stephen Cook, dass SAT NP-vollständig ist, und 1972 veröffentlichte Richard Karp seine 21 Probleme.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Komplexitätstheorie
• Wikipedia: Entscheidungsproblem
• Wikipedia (englisch): Karp’s 21 NP-complete problems
• Michael Sipser: Introduction to the Theory of Computation, Cengage Learning.
• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press.