Paper by Erik D. Demaine

Erik D. Demaine and Jenny Diomidova, “Strings-and-Coins and Nimstring are PSPACE-complete”, Integers: Electronic Journal of Combinatorial Number Theory, volume 21b, 2021, A7. The John Conway, Richard Guy, and Elwyn Berlekamp Memorial Volume

We prove that Strings-and-Coins — the combinatorial two-player game generalizing the dual of Dots-and-Boxes — is strongly PSPACE-complete on multigraphs. This result improves the best previous result, NP-hardness, argued in Winning Ways. Our result also applies to the Nimstring variant, where the winner is determined by normal play; indeed, one step in our reduction is the standard reduction (also from Winning Ways) from Nimstring to Strings-and-Coins.

This paper is also available as arXiv:2101.06361 and from the journal or Zenodo.

The paper is available in PDF (274k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.