On 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 <b>EXP</b>-complete and requires time <inline-formula><math xmlns="http://www.w3...
Main Authors: | Vladimir Gurvich, Mikhail Vyalyi |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2021-02-01
|
Series: | Algorithms |
Subjects: | |
Online Access: | https://www.mdpi.com/1999-4893/14/3/71 |
Similar Items
-
A linear algorithm for the restricted subtraction games
by: Zongbao Yang, et al.
Published: (2022-11-01) -
Agents, games, and evolution : strategies at work and play /
by: Kimbrough, Steve
Published: (c201) -
Addition and subtraction /
by: 433902 Leblanc, John F.
Published: (1976) -
Recognizing the Repeatable Configurations of Time-Reversible Generalized Langton’s Ant Is PSPACE-Hard
by: Takeo Hagiwara, et al.
Published: (2011-01-01) -
A subtraction game to scaffold primary students’ word problem solving skills
by: Evrim Erbilgin, et al.
Published: (2022-08-01)