Hyperbolic Minesweeper is in P

• Published in 2020
• Added on 2023-08-14

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.

Links

• http://arxiv.org/abs/2002.09534v2
• http://arxiv.org/pdf/2002.09534v2

Other information

BibTeX entry

@article{HyperbolicMinesweeperisinP,
	key = {HyperbolicMinesweeperisinP},
	type = {article},
	title = {Hyperbolic Minesweeper is in P},
	author = {Eryk Kopczy{\'{n}}ski},
	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.},
	comment = {},
	date_added = {2023-08-14},
	date_published = {2020-12-07},
	urls = {http://arxiv.org/abs/2002.09534v2,http://arxiv.org/pdf/2002.09534v2},
	collections = {computational-complexity-of-games},
	url = {http://arxiv.org/abs/2002.09534v2 http://arxiv.org/pdf/2002.09534v2},
	year = 2020,
	urldate = {2023-08-14},
	archivePrefix = {arXiv},
	eprint = {2002.09534},
	primaryClass = {cs.CC}
}