Hyperbolic Minesweeper is in P
arXiv:2002.09534v24 citations
Originality Incremental advance
AI Analysis
This resolves a theoretical problem in computational complexity for researchers, showing that hyperbolic geometry can simplify certain constraint satisfaction puzzles, though it is incremental as it builds on known NP-completeness results.
The paper tackled the computational complexity of a hyperbolic variant of Minesweeper, proving that it is in P (polynomial time) while the standard version is NP-complete, with the result applying broadly to puzzles based on local constraints on hyperbolic graphs.
We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.