P=NP=Minesweeper (Update)

Der britischer Mathematik-Professor Richard Kaye glaubt, mittels Minesweeper das Problem der NP-Vollständigkeit lösen zu können.

In Pocket speichern vorlesen Druckansicht 92 Kommentare lesen
Lesezeit: 2 Min.
Von
  • Markus Stöbe

Bereits Mitte letzten Monats hatte der ukrainische Mathematiker Anatoly D. Plotnikov angegeben, möglicherweise einen Lösungsansatz für das Problem der NP-Vollständigkeit gefunden zu haben. Nun behauptet auch der Mathe-Professor Richard Kaye der University of Birmingham in London, einer Lösung nahe zu sein: Seiner Meinung nach liegt die Lösung im populären Denkspiel Minesweeper.

Bei Minesweeper versucht der Spieler herauszufinden, in welchen Feldern der Spielmatrix (virtuelle) Minen plaziert sind. Als Hilfe wird ihm nur die Anzahl aller in den acht angrenzenden Feldern versteckten Minen angezeigt. Wenn es nun jemandem gelänge, alle möglichen Platzierungskombinationen für die Minen auf einem überdimensional großen Spielfeld per Algorithmus zu bestimmen, habe man laut Kaye auch die Lösung des P=NP-Problems.

NP-vollständige Probleme sind nicht in polynomiellem Zeitaufwand lösbare Probleme. Besonders die theoretischen Informatiker und Mathematiker interessieren sich für dieses Phänomen, den solche Aufgaben gelten bisher als von Computern nicht in vertretbarer Zeit lösbar. Sobald aber eines dieser Probleme per Algorithmus gelöst werden könnte, ließen sich alle Probleme dieser Klasse per Rechner lösen. Aus diesem Grund hat das Clay Institut für Mathematik, an dem Kaye beschäftigt ist, eine Belohnung von einer Million US-Dollar für die Lösung ausgeschrieben.

Bis es eine Lösung des mittlerweile rund 30 Jahre alten Problems gibt, werden sicher noch ein paar Jahre vergehen – falls sich nicht die Lösung von Plotnikov als richtig herausstellt. Interessierte sollten aber angesichts des ausgesetzten Preisgelds vielleicht doch die Augen offen halten und gegebenenfalls die Bemühungen nach einer eigenen Lösung intensivieren. (mst)