Strings-and-Coins and Nimstring are PSPACE-complete

01/16/2021
by   Erik D. Demaine, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset