Impossible Math Question?

[Tps222]

Originally Posted by www.minesweeper.com who took it from some other site

If you want a million dollars, the Clay Mathematics Institute is offering such to anyone who can
solve Minesweeper efficiently. Unfortunately, this is much harder than simply finishing a game.

Richard Kaye, of Birmingham University, proved that Minesweeper is an NP-complete problem.
If one NP-complete problem can be solved efficiently then all can be solved. Most mathematicians
do not believe this is possible. If you prove this to be the case you will also win the money.

P problems can be solved in polynomial time: when you increase the number of choices, the
solving time increases by a determined power. The goal is to prove P=NP.

A famous NP problem is a travelling salesman who must find the shortest route to visit several
cities. Simple at first, but the number of potential routes and the time to analyse them increases
drastically! After only 10 cities there are 3628800 routes to analyse. After 100 cities your
algorithm must scan 9.3 x 10157 possible routes. This is greater than the number of atoms in the
universe: the military uses NP codes because you will not live to find the solution!

However, if you could write a Minesweeper solver where the calculations, thus time, only
increased by a power, you would have created a very efficient solver.

Interestingly, this may still mean some problems will not be solveable in your lifetime. Yet, it
also means military codes can be cracked and you could earn a lot more than a million dollars!

I'm not in a high enough math to even attempt to think of the solution, but I know a lot of you are great at it. To me, it seems quite impossible and pointless, but if want to give it a go, I'd like to see your train of thought. Note:I realize many of the world's greatest mathematicians say there isn't a solution.