Web

Minesweeper - die Lösung für "P = NP?"

03.11.2000
Der britische Mathematiker Richard Kaye hofft mit Hilfe der Windows-Dreingabe "Minesweeper" einem der größten Rätsel seiner Wissenschaft auf die Spur zu kommen. "P = NP?" beschäftigt sich mit der Frage, ob es für scheinbar unlösbare Probleme nicht doch eine (Computer-)Lösung gibt.

MÜNCHEN (COMPUTERWOCHE) - Richard Kaye, Mathematikprofessor an der Universität Birmingham, ist der Ansicht, dass Microsofts Windows-Urspiel "Minesweeper" möglicherweise die Lösung für eines der größten Rätsel seiner Wissenschaft liefern könnte. Das "P = NP?"-Problem beschäftigt sich damit, ob eine Menge finiter Objekte eines bestimmten Typs, die in einer finiten Sprache kodiert und von einer nicht-deterministischen Turing-Maschine in polynomialer Zeit akzeptiert werden, auch von einer terministischen Maschine in polynomialer Zeit gelöst werden können. Nochmal auf Deutsch: Ist es möglich, dass es für ein scheinbar unlösbares Problem vielleicht doch eine simple Lösung gibt (möglicherweise mit Hilfe eines Computers)?

Kaye zumindest kam nach vielen Stunden Minesweeper die Erkenntnis, dass wer einen Algorithmus für alle denkbaren Minen-Platzierungen auf einem großen Spielfeld fände, gleichzeitig auch die Lösung für P = NP? Hätte. Und das wäre finanziell durchaus lukrativ - denn das Clay Mathematics Institute aus Cambridge, Massachusetts, hat dafür eine Million Dollar ausgelobt. Kayes Kollege Ian Stewart von der University of Warwick kommentiert: "Es ist verwunderlich, dass ein so einfaches Spiel uns so tief in die Mathematik hineinbringt. Aber die großen Fragen unseres Fachs liegen oft gar nicht tief unter der Alltagsoberfläche verborgen."