• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Computational hardness of multidimensional subtraction games

P. 237-249.

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.