What is the Minesweeper Consistency Problem?
This is a question one can ask about any particular rectangular grid with the squares decorated by numbers 0–8, mines, or left blank. It asks: is there a configuration of mines in the grid that would result in the pattern of symbols one sees (according to the usual Minesweeper rules)? The word “problem” here may be misleading. Think of it as a specification for an algorithm or computer program. There are certainly computer programs that meet this specification. (For instance, one can simply search through all possibilities, though this may take rather a long time to do!) The classes P and NP are certain classes of such problems (or specifications) with yes/no answers like this, and reformulating Minesweeper in terms of such a specification helps greatly in its analysis. By my result, the “P=NP”? question is equivalent to the question of whether there is a polynomial time algorithm that meets the specification in the Minesweeper Consistency Problem.
