Wenn Sie als Erster ein schnelles Lösungsverfahren für ein verbreitetes Computerspiel angeben, ernten Sie Ruhm, Ehre und viel Geld.
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. Gena
Spektrum der Wissenschaft
