Slashdot Mirror
Using Minesweeper to Solve NP
Blue Leader writes "Boston.com is reporting that the answer to one of math's most vexing problems lies in Minesweeper. Figure it out, and render modern encryption useless." Its a discussion of NP/P, as well as an excuse to play minesweeper. Personally, I kinda prefer mahjongg or tetris tho ;)
It's worth pointing out that the Boston.com does gloss over some fairly important mathematics.
All that Kaye has done is show that Minesweeper is NP complete. He has not yet found a polynomial-time solution to it, which is necessary to prove that P=NP -- in a nutshell, he just shows that Minesweeper falls into an equivalence class that holds a hell of a lot of other algorithms.
And EVEN IF HE FINDS the polynomial solution to Minesweeper, that STILL doesn't say anything about RSA (or any other "hard" algorithm), other than that it can be solved in polynomial time SOMEHOW.
The only reason people focus on this conjecture is they hope that proving P=NP and solving some algorithm will give them some magic insight into speeding up some other algorithm that's equivalently hard, rather than working on the algorithm directly. Or, disproving P=NP once and for all, and ensuring the computational assumptions that make people pick algorithms like RSA.
...was included with windows to give you something to favourably compare the 'bomb' rate to.
Comparisons:
Minesweeper:
- often explodes on the first click
- randomly explodes later on
- game is over quite quickly
- you have to press the reset button to restart
Windows:
- often explodes on the first click
- randomly explodes later on
- game is over quite quickly
- you have to press the reset button to restart
Its the same program!
Therefore- the Stability of Windows is NP complete! QED!
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"The author of this paper has a web page here:
:)
He also has a page specifically about this Minesweeper business here.
I like the other paper proving that minesweeper, with a little variation, on an infinite board, is Turing-complete. Fun!
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
As with almost any mass media article about mathematics, this article is full of errors that nitpicky people like me feel the need to point out. First of all, some basic info you may be lacking. The basic P vs. NP problem is most simply stated as "P = NP?" P stands for Polynomial time, and NP stands for Nondeterministic Polynomial time, as in you can solve the problem is p(n) steps, where p is a polynomial and n is the size of the input file. Beyond that, some heinous mistakes they made: 1. P is a subset of NP, not a distinct set. Thus all P problems are NP (obviously, if you read the definition). 2. Internet encryption (at least RSA) is NOT KNOWN TO BE EVEN NP-COMPLETE. This is something I think a lot of people don't realize, and I have talked to many mathematicians who think that factorization will eventually be shown to be in P and thus RSA and all other such encryption schemes will collapse. All it takes is one brilliant hacker... 3. The answer has to do with determining consistency, which is very, very different from solving the game in a game theoretical sense. And some slightly more nitpicky issues: 1. NP-Complete problems are those problems whose solutions can be polynomial time transformed to solutions to _any_ other problem. That is why if you find a solution to the minesweeper problem, NP-Complete will cease to exist and P=NP. 2. No serious mathematician believes that P=NP. Anyone who wants to know more should read Sipser's book "Introduction to the Theory of Computation" which I highly recommend.
RSA is only NP, or at least nobody's proven it to be NP-Complete yet.
Any NP-Complete problem can be transformed into any other NP-Complete problem via a polynomial time transformation. Thus, solving one solves all. I have no idea how to do it, it's over my head. But it can be done.
Anyway, more to the point, this isn't about Minesweeper, it's a problem called the "MineSweeper Consistentcy Problem" and it's important to remember that. Essentially, the MCP is: given a half finished minesweeper board, is it consistent? That is, is it a valid board within the rules of the game? It is possible to get this board through normal play?
That's a bit of a different beast than just playing the game, guys.
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.