One of the biggest unsolved math problems is the P versus NP problem. Essentially, the problem asks,

“Suppose that solutions to a problem can be verified quickly. Then, can the solutions themselves also be computed quickly?”

In other words, if P (easy to find) = NP (easy to check), then problems that can be verified in polynomial time could aso be solved in polynomial time. If P does not equal NP, then some problems that could not be solved in polynomial time could still be verified in polynomial time. And more simply put, problems of type P are easy, but type NP problems are hard, because they cannot be solved algorithmically because any practical algorithmic solution would take far too long to get a solution.

This problem is one of the Clay Mathematics Institutes’ Millenium Problems.

Now how does Minesweeper potentially help solve the problem? For those who don’t know, Minesweeper is an old computer game, where the object is to clear an abstract minefield without detonating a mine. The player starts with a grid of blank squares, and underneath some random squares are mines. Clicking on a square either reveals a mine, in which case you lose, or a number is revealed that indicates the number of the 8 adjacent squares that contain mines.

I’ll spare many details, because I’ve already written a lot, but a man named Richard Kaye has proven that Minesweeper is NP-complete, which means the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. But if anyone can analyze the game enough to provide a valid solution to the P=NP (or prove there isn’t one, I suppose) problem using an infinitely large Minesweeper board, there is a hefty prize awaiting. Happy gaming!

About these ads