QED

Richard Kaye bewees in 2000 dat het spelen van het computerspelletje Mijnenveger een NP-volledig probleem is (“Minesweeper is NP-complete”, Mathematical Intelligencer, Vol. 22, No. 2 (2000), pp. 9-15). Op zijn webpagina hierover zegt hij:

[T]he fact that it is NP-complete means, for Minesweeper fans, that their favourite game can be seen as being right at the cutting edge of mathematical research.

Wat betekent dit voor de mensen die dit spel spelen? Van de ene kant kan je zeggen dat het bewijs van Kaye aantoont dat Mijnenveger een moeilijk spel is:

In some sense, when you play the game you cannot be expected to do much better than the hundreds of very good mathematicians who have worked on the P=NP? question for many many years.

Kaye droomt echter ook van een andere mogelijkheid:

The more exciting view one might take is that one day, perhaps, it may turn out that an expert Minesweeper player could spot some pattern in the game that would eventually lead to an polynomial-time algorithm for solving it—and hence polynomial-time algorithms for all the NP-complete problems. Such an outcome would result in methods to crack all of the codes used in the internet and computers across the world.

Hij heeft ook een interessante FAQ over het onderwerp en heeft bovendien bewezen dat een oneindig mijnenvegerveld Turing-volledig is en dus elk computerprogramma kan simuleren.