Das Clay Mathematics Institute, eine gemeinnützige Bildungseinrich tung in Cambridge (Massachusetts), hat Preise von jeweils einer Million Dollar für die Lösung von sieben prominenten mathematischen Problemen ausgesetzt. Eines von ihnen ist eine Frage aus der Komplexitätstheorie, die allgemein nur in sehr abstrakter Form ausgedrückt wird: Ist P=NP oder nicht? Jahrzehntelang haben sich die Mathematiker die Zähne daran ausgebissen, aber fast jeder Besitzer eines PCs hat ein Mittel an der Hand, es zu lösen – theoretisch. Es handelt sich um das Computerspiel "Minesweeper" ("Minensucher").

Richard Kaye von der Universität Birmingham (England) hat kürzlich auf Verbindungen zwischen diesem Spiel und dem berühmten Problem in einem Artikel hingewiesen ("Mathematical Intelligencer", Bd. 22, Nr. 2, Frühjahr 2000, S. 9). Die Spielregeln sind wie folgt. Der Computer beginnt das Spiel und zeigt auf dem Bildschirm eine rechteckige Anordnung von Feldern. Unter einigen liegen explosive Minen, und es gilt herauszufinden, unter welchen. Im ersten Zug decken Sie irgendein Feld auf. Wenn sich darunter eine Mine befindet, explodiert sie, und Sie haben verloren. Wenn nicht, schreibt der Computer eine Zahl in das aufgedeckte Feld, die Ihnen sagt, wie viele Minen unter den acht angrenzenden Feldern liegen.

Mit dieser Information wählen Sie das nächste aufzudeckende Feld. Wieder knallt es, oder der Computer zeigt die Zahl der Minen in den angrenzenden Feldern an. Wenn Sie herausgefunden haben, dass unter einem Feld eine Mine liegt, können Sie dieses mit einem Fähnchen kennzeichnen. Wenn Sie alle Minen gefunden haben, sind Sie der Gewinner.

Was hat das nun damit zu tun, ob P=NP ist? Eine zentrale Frage der Komplexitätstheorie ist, wie schnell ein Algorithmus, das heißt ein schrittweises, auf einem Computer ausführbares Verfahren, ein gegebenes Problem lösen kann. Genauer gefragt: Wie hängt die Laufzeit – zu messen als die Anzahl der Rechenschritte bis zur Lösung – von der Problemgröße ab, das heißt von der Anzahl der Anfangsdaten? Es versteht sich, dass ein Problem umso mühsamer zu lösen ist, je mehr Daten es enthält: Zwei dreißigstellige Zahlen zu multiplizieren kostet mehr Arbeit als zwei fünfzehnstellige; um ein 1000-Teile-Legepuzzle fertig zu stellen, braucht man weitaus mehr Zeit als für ein 500-Teile-Puzzle. Die entscheidende Frage ist jedoch, wie schnell die Laufzeit mit der Problemgröße anwächst.

Die Klasse P der leichten Probleme

Bei der Multiplikation ist es eine Potenz der Problemgröße n: Um zwei n-stellige Zahlen zu multiplizieren, braucht es im Wesentlichen n2 elementare Rechenschritte. Probleme dieser Art werden "vom Typ P" genannt (das P steht für "polynomiale Laufzeit") und gelten als leicht. Richtig schwer sind erst die Probleme, bei denen der Aufwand schneller steigt als jede Potenz von n, beispielsweise proportional zu 2n oder zu n! (n-Fakultät). Das kommt insbesondere dann vor, wenn die richtige Reihenfolge von n Daten gesucht ist und ein Algorithmus nichts Besseres tun kann, als alle Reihenfolgen durchzuprobieren. Ein Problem, das nicht vom Typ P ist, überfordert bereits bei mäßiger Größe die besten Computer der Welt.

Man kann beweisen, dass ein Problem vom Typ P ist, indem man einen Algorithmus angibt, der es in polynomialer Zeit löst. Solche Algorithmen gibt es beispielsweise für die Aufgabe, eine Reihe von Zahlen nach der Größe zu sortieren; entsprechend schnell arbeiten kommerzielle Sortierprogramme selbst auf großen Datenmengen. Das Problem des Handlungsreisenden – eine kürzeste Rundreise durch eine gegebene Menge von Städten zu finden – ist dagegen anscheinend nicht vom Typ P, aber das hat bisher noch niemand bewiesen. Gleiches gilt für die Aufgabe, die Primfaktoren einer natürlichen Zahl zu finden.

Warum ist es so schwer zu beweisen, dass ein Problem nicht vom Typ P ist? Weil es nicht genügt, einen bestimmten Algorithmus zu analysieren. Man müsste vielmehr zeigen, dass unter allen überhaupt denkbaren Algorithmen keiner das Problem in polynomialer Zeit lösen kann, und das ist sehr schwer. Das Beste, was bisher erreicht wurde, ist zu beweisen, dass eine ganze Reihe anscheinend schwerer Probleme miteinander verwandt sind: Wenn man eines davon in polynomialer Zeit lösen kann, dann auch alle anderen. Diese Probleme gehören sämtlich zu einer Klasse namens NP (für nichtdeterministisch polynomial).

NP ist nicht dasselbe wie Nicht-P. Ein Problem ist definitionsgemäß vom Typ NP, wenn man in polynomialer Zeit nachprüfen kann, ob eine vorgeschlagene Lösung richtig ist. Das ist offensichtlich weitaus einfacher, als die Lösung zu finden. Die Teile eines Legepuzzles richtig zusammenzulegen ist sehr mühsam – der Aufwand für das Durchprobieren wächst mit der Anzahl der Teile ins Gigantische; aber wenn jemand behauptet, das geschafft zu haben, braucht man nur für jedes Teil nachzusehen, ob es mit seinen Nachbarn zusammenpasst. Die dafür benötigte Zeit ist ungefähr proportional zur Zahl der Teile, also ist die Überprüfung in polynomialer Zeit zu erledigen.

Es stellt sich nun heraus, dass viele NP-Probleme ineinander umformbar sind. Aus einem Algorithmus zur Lösung des einen Problems kann man demnach ohne weiteres einen machen, der das andere löst, und zwar in derselben Zeit – bis auf einen konstanten Faktor, und auf konstante Faktoren kommt es in dieser Theorie nicht an. Man nennt ein Problem NP-vollständig, wenn die Existenz eines polynomialen Lösungsalgorithmus für dieses Problem nach sich zieht, dass alle NP-Probleme in polynomialer Zeit lösbar sind. Die NP-vollständigen Probleme bilden also eine besonders interessante Unterklasse der NP-Probleme: Wenn Sie ein einziges dieser speziellen Probleme in polynomialer Zeit lösen können, dann haben Sie auf einen Schlag eine ganze Klasse schwerer Probleme (NP) in leichte (P) verwandelt.

Sind also die allem Anschein nach schweren Probleme eigentlich leicht? Ist P=NP? Jedermann erwartet die Antwort "Nein", aber wenn sich irgendein NP-vollständiges Problem als vom Typ P erweist, dann muss P=NP sein.

Man kennt sehr viele NP-vollständige Probleme. Eines der wichtigsten ist das Erfüllbarkeitsproblem (satisfiability problem, SAT). Nehmen wir als Beispiel eine Gesetzesvorschrift: Ein Mensch ist asylberechtigt, wenn er eine Reihe von Voraussetzungen erfüllt ODER eine andere Reihe von Voraussetzungen ODER eine dritte Reihe ? Die Voraussetzungen schließen sich zum Teil gegenseitig aus. Gibt es eine Kombination von Voraussetzungen, die einen asylberechtigt macht?

Dasselbe wäre formal wie folgt auszudrücken. Gegeben ist ein großer, komplizierter Schaltkreis (die Gesetzesvorschrift). An den Eingängen des Schaltkreises (den "Voraussetzungen") kann jeweils der Wert W (wahr) oder F (falsch) anliegen. Der Schaltkreis selbst besteht aus logischen Schaltelementen (Gattern) mit Namen wie UND, ODER und NICHT. Jedes Gatter kombiniert seine Eingaben in bestimmter Weise und liefert das Ergebnis als Ausgabe, die vielleicht einem weiteren Gatter als Eingabe dient. So verwandelt ein NICHT-Gatter eine Eingabe W in die Ausgabe F und umgekehrt; ein UND-Gatter liefert genau dann die Ausgabe W, wenn beide Eingänge W sind. Der ganze Schaltkreis hat einen einzigen Ausgang (die "Entscheidung"), und das SAT-Problem ist die Frage, ob es zu einem gegebenen Schaltkreis eine Kombination von Eingaben gibt, die an diesem Ausgang ein W erzeugen. Für einfache Schaltkreise ist das ein Kinderspiel, aber bei vielen Gattern und vielen Eingaben schier unlösbar.

Der Zusammenhang mit dem Computerspiel Minesweeper wird ersichtlich, wenn wir nun das Minesweeper-Konsistenzproblem betrachten. Hier geht es nicht darum, die Minen zu finden, sondern herauszufinden, ob eine gegebene Minesweeper-Position logisch konsistent ist. Wenn Sie beispielsweise im Spielverlauf auf die im Kasten rechts gezeigte Position stoßen sollten, wüssten Sie sofort, dass der Programmierer einen Fehler gemacht hat. Keine Verteilung von Minen könnte mit den gezeigten Zahlen in den Feldern übereinstimmen.

Das Minesweeper-Problemist echt schwer

In einem gewöhnlichen Minesweeper-Spiel löst der Spieler immer wieder (kleine) Konsistenzprobleme: Ist die Annahme, unter einem bestimmten Feld stecke eine Mine, mit den bereits bekannten Zahlen vereinbar? Wäre also die Spielstellung mit der Mine in diesem Feld konsistent? Wenn nein, dann darf der Spieler das Feld getrost betreten.

In seinem Artikel beweist Kaye, dass das SAT-Problem für einen gegebenen logischen Schaltkreis sich in ein Minesweeper-Konsistenzproblem für eine bestimmte Spielposition umformen lässt. Darüber hinaus zeigt er, dass diese Umformung in polynomialer Zeit abläuft.

Bei dieser Prozedur wird der komplette Schaltkreis in eine Position auf einem (möglicherweise sehr großen) Mine-sweeper-Brett abgebildet. Ein Gatter wird zu einer Anordnung von Feldern; einige von ihnen sind aufgedeckt und tragen Nummern, andere sind vermint, was aus den Einträgen in den Nachbarfeldern eindeutig hervorgeht, und wieder andere sind verdeckt, und es ist zunächst unklar, ob eine Mine darunter liegt (was dem Wert W entspricht) oder nicht (F). Ein Draht ist ebenfalls eine (lang gestreckte) Anordnung von Minesweeper-Feldern. Drähte, die um die Ecke gehen, sich verzweigen oder sich überkreuzen, sind durch spezielle Minesweeper-Konfigurationen wiederzugeben. Kaye gelingt es in seinem Artikel, alle diese Probleme zu lösen. Am Ende ist aus dem Erfüllbarkeitsproblem zunächst ein logischer Schaltkreis und aus diesem eine Stellung auf einem (sehr großen) Minesweeper-Brett geworden. Wenn man das Konsistenzproblem für diese Spielposition in polynomialer Zeit lösen kann, dann hat man in derselben Zeit auch das zugehörige SAT-Problem gelöst.

Mit anderen Worten: Das Minesweeper-Konsistenzproblem ist NP-vollständig. Wenn jemand also für dessen Lösung einen polynomialen Algorithmus findet, dann lassen sich alle NP-Probleme in polynomialer Zeit lösen, und dann ist P=NP. Wenn andererseits jemand zeigen kann, dass es keinen solchen Algorithmus gibt, dann ist P?NP.

Ehe Sie sich aber Hoffnung machen, seien Sie gewarnt: Das Minesweeper-Konsistenzproblem ist eine harte Nuss! Für gigantische Gitter wird es äußerst schwierig, und die meisten Fachleute sind davon überzeugt, dass es keinen Lösungsalgorithmus mit polynomialer Laufzeit gibt. Außerdem hat das Clay Institute strikte Regeln für den Wettbewerb aufgestellt. Bevor eine Lösung als richtig akzeptiert wird, muss sie in einer angesehenen mathematischen Zeitschrift veröffentlicht und innerhalb von zwei Jahren nach der Publikation "allgemein akzeptiert" sein.

Aus: Spektrum der Wissenschaft 5 / 2002, Seite 114
© Spektrum der Wissenschaft Verlagsgesellschaft mbH