Computer Science – Computational Complexity
Scientific paper
2012-04-20
Computer Science
Computational Complexity
14 pages, LaTeX => DVI => PS => PDF
Scientific paper
We show that the Minesweeper game is PP-hard, when the object is to locate all mines with the highest probability. When the probability of locating all mines may be infinitesimal, the Minesweeper game is even PSPACE-complete. In our construction, the player can reveal a boolean circuit in polynomial time, after guessing an initial square with no surrounding mines, a guess that has 99 percent probability of success. Subsequently, the mines must be located with a maximum probability of success. Furthermore, we show that determining the solvability of a partially uncovered Minesweeper board is NP-complete with hexagonal and triangular grids as well as a square grid, extending a similar result for square grids only by R. Kaye. Actually finding the mines with a maximum probability of success is again PP-hard or PSPACE-complete respectively. Our constructions are in such a way that the number of mines can be computed in polynomial time and hence a possible mine counter does not provide additional information. The results are obtained by replacing the dyadic gates in [3] by two primitives which makes life more easy in this context.
No associations
LandOfFree
The computational complexity of Minesweeper does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The computational complexity of Minesweeper, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computational complexity of Minesweeper will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-6002