Paper by Erik D. Demaine

Reference:

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

BibTeX

@Article{StringsCoins_Integers,
  AUTHOR        = {Erik D. Demaine and Jenny Diomidova},
  authororig    = {Erik D. Demaine and Yevhenii Diomidov},
  TITLE         = {{Strings-and-Coins} and {Nimstring} are {PSPACE}-complete},
  JOURNAL       = {Integers: Electronic Journal of Combinatorial Number Theory},
  VOLUME        = {21b},
  PAGES         = {A7},
  YEAR          = 2021,
  NOTE          = {The John Conway, Richard Guy, and Elwyn Berlekamp Memorial Volume},

  doi           = {https://dx.doi.org/10.5281/zenodo.10939674},
  comments      = {This paper is also available as <A HREF="https://arxiv.org/abs/2101.06361">arXiv:2101.06361</A> and from <A HREF="https://math.colgate.edu/~integers/vol21b.html">the journal</A> or <A HREF="https://dx.doi.org/10.5281/zenodo.10939674">Zenodo</A>.},
  withstudent   = 1,
}

Abstract:

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.

Comments:

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

Availability:

The paper is available in PDF (274k).

See information on file formats.

[Google Scholar search]