Thoughtlessly Thought Thoughts

Jeder kennt Minesweeper, das Spiel, das schon in Windows 3.0 (oder noch früher) für Produktivitätsverluste von Menschen an Bildschirmarbeitsplätzen veranwortlich war. Heute kommt noch Instant Messaging wie etwa ICQ hinzu, um den IQ noch weiter zu senken!

Doch - Minesweeper-Spieler aufgepasst! Wenn ihr meint, dass ihr das Spiel sehr effizient lösen könnt, dann winken euch eine Millionen US-Dollar. Eine Million? Ja, genau! Kaye wies 2000 nach, dass Minesweeper NP-vollständig ist.

Könnt ihr Minesweeper in polynomieller Zeit - also etwa O(n⁴²) lösen (n sei die Kantenlänge eines quadratischen Spielfeldes), dann habt ihr gezeigt, dass P = NP gilt. Toll - was! Leider steht der Beweis wohl nicht online, aber die ganz Hartgesottenen können ja mal versuchen sich Volume 22 number 2 vom Mathematical Intelligencer in einer Bibliothek zu besorgen. Wem das zu mühsam ist, oder eine etwas lockerere Erklärung möchte, der kann sich eine populärwissenschaftliche Erklärung auf den Seiten des Clay Math Institute durchlesen. Alle anderen bleiben unwissend.

Kudos an Anstei