Computational hardness of multidimensional subtraction games
We study the 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 solving the game is (formula presented)-complete and requires time (formula presented), where n is the input size. This bound is optimal up to a polynomial speed-up. The results are based on the construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata. © Springer Nature Switzerland AG 2020.