论文标题
多维减法游戏的计算硬度
Computational Hardness of Multidimensional Subtraction Games
论文作者
论文摘要
我们研究以有限差的固定维度解决减法游戏的算法复杂性。我们证明了该课程中存在的游戏，因此任何解决游戏的算法都在指数时间内运行。另外，我们证明了该课程中的游戏存在，因此解决游戏是Pspace-Hard。结果基于Larsson和Wästlund引入的施工。它与减法游戏和蜂窝自动机有关。
We study algorithmic complexity of solving subtraction games in a~fixed dimension with a finite difference set. We prove that there exists a game in this class such that any algorithm solving the game runs in exponential time. Also we prove an existence of a game in this class such that solving the game is PSPACE-hard. The results are based on the construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata.
