Interesting Esoterica

Hyperbolic Minesweeper is in P

Article by Eryk KopczyƄski
  • Published in 2020
  • Added on
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

Other information

key
HyperbolicMinesweeperisinP
type
article
date_added
2023-08-14
date_published
2020-07-11

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-07-11},
	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}
}