randform

image from wikipedia
This is a followup to the last quantum computer post.

The computer game Minesweeper (here also a Java applet) plays an important role in complexity theory.

In particular the question wether a given state during a game of Minesweeper has no intrinsic contradictions (between known bomb positions and indicated ones) is probably not solvable within a decent time (via a computer algorithm): Minesweeper is a so-called NP-complete problem and NP-complete problems can probably not be solved in polynomial time.

However if you could eliminate the word probably in my above sentence then you could earn 1 million dollar (and probably more than that). The above problem is called the NP versus P problem and one of the seven millenium prize problems in math (here P stands for problems that can be solved in polynomial time and NP for problems for which one can verify a solution in polynomial time). Details on how to win are on this very nicely written Millenium prize site.

So in short: It is generally BELIEVED that NP is NOT P, but the proof hasn’t been done yet, i.e. the Minesweeper problem is still somewhat open.

Why is this at all a thrilling problem? This is because 1) one wants computers to solve problems in a decent time (also if this seems not so probable) and 2) because if one proves the above for one NP-complete problem than one proved it for all NP problems, which are quite a big class of problems. So a proof about the solvability of the Minesweeper problem gives a decision about the solvability of a lot of other problems. But sofar we have to live on without a proof, i.e. with an open problem.

For those who yet don’t know this is how the game Minesweeper works:
(citation from the Millenium prize site)

The computer starts the game by showing you a blank grid of squares. Some squares conceal mines; the rest are safe. Your task is to work out where the mines are without detonating any of them. You do this by choosing a square. If there’s a mine underneath it, the mine is detonated and the game ends — – with a loss for you, of course. If there is no mine, however, the computer writes a number in that square, telling you how many mines there are in the eight immediately adjacent squares (horizontally, vertically, and diagonally).

If your first guess hits a mine, you’re unlucky: you get no information except that you’ve lost. If it doesn’t, though, then you get partial information about the location of nearby mines. You use this information to influence your next choice of square, and again either you detonate a mine and lose, or you gain information about the positions of nearby mines.

posted by nad on Monday, February 19th, 2007 at 10:17 am // games, math, software. // RSS 2.0 feed skip to the end and leave a response // pinging is currently not allowed //