论文标题
双曲线扫雷在P中
Hyperbolic Minesweeper is in P
论文作者
论文摘要
我们表明，虽然扫雷器是NP完整的，但其双曲线变体位于P中。我们的证明不依赖于扫雷器的规则，而是基于满足双曲线平面中嵌入的图的局部约束的任何难题。
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.
