Wer wird Millionär?
Wenn Sie als Erster ein schnelles Lösungsverfahren für ein verbreitetes Computerspiel angeben, ernten Sie Ruhm, Ehre und viel Geld.
Ian Stewart
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


abrufen




NeuroKognition |
RELATIV EINFACH |
Go for Launch |
Natur des Glaubens |
Medicine & More | 




