Computational Hardness of Multidimensional Subtraction Games

01/12/2020
by   Vladimir Gurvich, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset