{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:50:30Z","timestamp":1760233830942,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T00:00:00Z","timestamp":1614211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["20-11-20203"],"award-info":[{"award-number":["20-11-20203"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 EXP-complete and requires time 2\u03a9(n), where n is the input size. This bound is optimal up to a polynomial speed-up. The results are based on a construction introduced by Larsson and W\u00e4stlund. It relates subtraction games and cellular automata.<\/jats:p>","DOI":"10.3390\/a14030071","type":"journal-article","created":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T21:16:53Z","timestamp":1614287813000},"page":"71","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Computational Hardness of Multidimensional Subtraction Games"],"prefix":"10.3390","volume":"14","author":[{"given":"Vladimir","family":"Gurvich","sequence":"first","affiliation":[{"name":"Faculty of Computer Science\/Big Data and Information Retrieval School, HSE University, 109028 Moscow, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9822-1060","authenticated-orcid":false,"given":"Mikhail","family":"Vyalyi","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science\/Big Data and Information Retrieval School, HSE University, 109028 Moscow, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/1967631","article-title":"Nim, a game with a complete mathematical theory","volume":"3","author":"Bouton","year":"1901","journal-title":"Ann. Math."},{"key":"ref_2","unstructured":"Berlekamp, E.R., Conway, J.H., and Guy, R.K. (2001). Winning Ways for Your Mathematical Plays. Vol. 1, A.K. Peters."},{"key":"ref_3","unstructured":"Conway, J.H. (1976). On Numbers and Games, Academy Press."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1017\/S0305004100031510","article-title":"Disjunctive games with the last player losing","volume":"52","author":"Grundy","year":"1956","journal-title":"Proc. Camb. Philos. Soc."},{"key":"ref_5","first-page":"199","article-title":"A modification of the game of Nim","volume":"7","author":"Wythoff","year":"1907","journal-title":"Nieuw Arch. Voor Wiskd."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(84)90012-4","article-title":"Wythoff games, continued fractions, cedar trees and Fibonacci searches","volume":"29","author":"Fraenkel","year":"1984","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1080\/00029890.1982.11995454","article-title":"How to beat your Wythoff games\u2019 opponent on three fronts","volume":"89","author":"Fraenkel","year":"1982","journal-title":"Am. Math. Mon."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1007\/s00182-012-0338-6","article-title":"A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory","volume":"42","author":"Boros","year":"2013","journal-title":"Int. J. Game Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"93","DOI":"10.2307\/1967321","article-title":"A generalization of the game called Nim","volume":"11","author":"Moore","year":"1910","journal-title":"Ann. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01784796","article-title":"The skeletion of an impartial game and the Nim-Function of Moore\u2019s Nimk","volume":"9","author":"Jenkyns","year":"1980","journal-title":"Int. J. Game Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.jcta.2019.02.006","article-title":"Sprague-Grundy Function of symmetric hypergraphs","volume":"165","author":"Boros","year":"2019","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2017.08.007","article-title":"On the Sprague-Grundy Function of Exact k-Nim","volume":"239","author":"Boros","year":"2018","journal-title":"Discret. Appl. Math."},{"key":"ref_13","unstructured":"Gurvich, V., and Ho, N.B. (2015). Slow k-Nim. In RUTCOR Research Report; RRR-03-2015; Rutegers University: New Brunswick, NJ, USA, 2015.k-Nim. RUTCOR Research Report, Rutegers University. RRR-03-2015."},{"key":"ref_14","unstructured":"Gurvich, V., Heubach, S., Ho, N.B., and Chikin, N. Slow k-Nim. Integers. Electron. J. Comb. Number Theory, Available online: https:\/\/scholars.latrobe.edu.au\/display\/publication1154216."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","article-title":"On the complexity of some two-person perfect-information games","volume":"16","author":"Shaefer","year":"1978","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_16","unstructured":"Demaine, E.D., and Hearn, R.A. (2008). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. CoRR, abs:0106019v2."},{"key":"ref_17","unstructured":"Boros, E., Gurvich, V., Ho, N.B., Makino, K., and Mursic, P. (2017). Tetris Hypergraphs and Combinations of Impartial Games. CoRR, abs:1701.02819."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.tcs.2019.09.041","article-title":"Sprague-Grundy Function of matroids and related hypergraphs","volume":"799","author":"Boros","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_19","first-page":"1642","article-title":"From heaps of matches to the limits of computability","volume":"20","author":"Larsson","year":"2013","journal-title":"Electron. J. Comb."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/S0021-9800(66)80016-9","article-title":"A mathematical investigation of games of \u201ctake-away\u201d","volume":"1","author":"Golomb","year":"1966","journal-title":"J. Combin. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"3169","DOI":"10.1016\/j.tcs.2010.05.007","article-title":"Invariant Games","volume":"411","author":"Rigo","year":"2010","journal-title":"Theoret. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Albert, M., Nowakowski, R., and Wolfe, D. (2007). Lessons in Play: An Introduction to Combinatorial Game Theory, Taylor & Franscis.","DOI":"10.1201\/b10691"},{"key":"ref_23","unstructured":"Hopcroft, J.E., Motwani, R., and Ullman, J.D. (2006). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Longman Publishing Co., Inc.. [3rd ed.]."},{"key":"ref_24","unstructured":"von Neumann, J., and Morgenstern, O. (1944). Theory of Games and Economic Behaviour, Princeton University Press."},{"key":"ref_25","unstructured":"Sipser, M. (2013). Introduction to the Theory of Computation, Cengage Learning."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/3242953.3242964","article-title":"A survival guide to Presburger arithmetic","volume":"5","author":"Haase","year":"2018","journal-title":"ACM SIGLOG News"},{"key":"ref_27","first-page":"27","article-title":"Super-Exponential Complexity of Presburger Arithmetic","volume":"Volume VII","author":"Karp","year":"1974","journal-title":"SIAM-AMS Proceedings. Complexity of Computation"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0304-3975(80)90037-7","article-title":"The complexity of logical theories","volume":"11","author":"Berman","year":"1980","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/71\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:28:29Z","timestamp":1760160509000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,25]]},"references-count":28,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["a14030071"],"URL":"https:\/\/doi.org\/10.3390\/a14030071","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,2,25]]}}}