Back to Search
Start Over
Hyperbolic Minesweeper is in P
- Source :
- 10th International Conference on Fun with Algorithms (FUN 2021)
- Publication Year :
- 2020
-
Abstract
- 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.<br />Comment: fixed an error in Corollary 5.6: planar graph -> (r,d)-hyperbolic graph
Details
- Database :
- arXiv
- Journal :
- 10th International Conference on Fun with Algorithms (FUN 2021)
- Publication Type :
- Report
- Accession number :
- edsarx.2002.09534
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.4230/LIPIcs.FUN.2021.18