Abstract
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 \({\mathbf {EXP}}\)-complete and requires time \(2^{\varOmega (n)}\), 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.
The article was prepared within the framework of the HSE University Basic Research Program. The second author was supported in part by RFBR grant 20-01-00645 and the state assignment topic no. 0063-2016-0003.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albert, M., Nowakowski, R., Wolfe, D.: Lessons in Play: An Introduction to Combinatorial Game Theory. Taylor & Francis, Abington (2007)
Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays, vol. 1–4. A.K. Peters, Natick (2001–2004)
Boros, E., Gurvich, V., Oudalov, V.: A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory. Int J. Game Theory 42(4), 891–915 (2013). https://doi.org/10.1007/s00182-012-0338-6
Boros, E., Gurvich, V., Ho, N.B., Makino, K., Mursic, P.: Tetris hypergraphs and combinations of impartial games. CoRR abs/1701.02819 (2017). http://arxiv.org/abs/1701.02819
Boros, E., Gurvich, V., Ho, N.B., Makino, K., Mursic, P.: On the Sprague-Grundy function of exact \(k\)-nim. Discrete Appl. Math. 239, 1–14 (2018)
Boros, E., Gurvich, V., Ho, N.B., Makino, K., Mursic, P.: Sprague-Grundy function of matroids and related hypergraphs. Theor. Comput. Sci. 799, 40–58 (2019)
Boros, E., Gurvich, V., Ho, N.B., Makino, K., Mursic, P.: Sprague-Grundy function of symmetric hypergraphs. J. Comb. Theory Ser. A 165, 176–186 (2019)
Bouton, C.L.: Nim, a game with a complete mathematical theory. Ann. Math. 2nd Ser. 3, 35–39 (1901–1902)
Conway, J.H.: On Numbers and Games. Academic Press, London, New York, San Francisco (1976)
Demaine, E.D., Hearn, R.A.: Playing games with algorithms: algorithmic combinatorial game theory. CoRR abs/cs/0106019v2 (2008). http://arxiv.org/abs/cs/0106019v2
Duchêne, E., Rigo, M.: Invariant games. Theor. Comput. Sci. 411, 3169–3180 (2010)
Fraenkel, A.: How to beat your Wythoff games’ opponent on three fronts. Am. Math. Mon. 89, 353–361 (1982)
Fraenkel, A.: Wythoff games, continued fractions, cedar trees and Fibonacci searches. Theor. Comput. Sci. 29, 49–73 (1984)
Golomb, S.W.: A mathematical investigation of games of “take-away”. J. Comb. Theory 1(4), 443–458 (1966)
Grundy, P.M., Smith, C.: Disjunctive games with the last player losing. Proc. Camb. Philos. Soc. 52, 527–533 (1956)
Gurvich, V., Heubach, S., Ho, N.B., Chikin, N.: Slow \(k\)-nim integers. Electron. J. Comb. Number Theory 20, 1–19 (2020)
Gurvich, V., Ho, N.B.: Slow \(k\)-nim. RUTCOR Research Report RRR-03-2015 (2015)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley Longman Publishing Co., Inc., Boston (2006)
Jenkyns, T.A., Mayberry, J.P.: The skeletion of an impartial game and the Nim-function of Moore’s Nim\({}_k\). Int J. Game Theory 9, 51–63 (1980). https://doi.org/10.1007/BF01784796
Larsson, U., Wästlund, W.: From heaps of matches to the limits of computability. Electron. J. Comb. 20(3), #P41 (2013)
Moore, E.: A generalization of the game called Nim. Ann. Math. Second Ser. 11(3), 93–94 (1910)
von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behaviour. Princeton University Press, Princeton (1944)
Shaefer, T.J.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16, 185–225 (1978)
Sipser, M.: Introduction to the Theory of Computation. Cengage Learning, Boston (2013)
Wythoff, W.: A modification of the game of Nim. Nieuw Archief voor Wiskunde 7, 199–202 (1907)
Acknowledgment
The authors are grateful to the anonymous referee for several helpful remarks improving both, the results and their presentation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Gurvich, V., Vyalyi, M. (2020). Computational Hardness of Multidimensional Subtraction Games. In: Fernau, H. (eds) Computer Science – Theory and Applications. CSR 2020. Lecture Notes in Computer Science(), vol 12159. Springer, Cham. https://doi.org/10.1007/978-3-030-50026-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-50026-9_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-50025-2
Online ISBN: 978-3-030-50026-9
eBook Packages: Computer ScienceComputer Science (R0)