Strings-and-coins and Nimstring are PSPACE-complete

zbMATH Open1490.91031arXiv2101.06361MaRDI QIDQ3390719FDOQ3390719

Authors: Erik D. Demaine, Yevhenii Diomidov 

Publication date: 25 March 2022

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.

Full work available at URL: https://arxiv.org/abs/2101.06361

Recommendations

• Strings-and-coins and nimstring are PSPACE-complete
• A PSPACE-complete graph nim
• PSPACE-Hardness of some combinatorial games
• Nimstring values for \(2\times n\) rectangular arrays. I
• On the complexity of the misère version of three games played on graphs

Mathematics Subject Classification ID

2-person games (91A05) Combinatorial games (91A46) Algorithmic game theory and complexity (91A68)

Cites Work

• On the complexity of some two-person perfect-information games
• Playing games with algorithms: algorithmic combinatorial game theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Narrow misère dots-and-boxes

Cited In (3)

• Strings-and-coins and nimstring are PSPACE-complete
• A PSPACE-complete graph nim
• Nimstring values for \(2\times n\) rectangular arrays. I

This page was built for publication: Strings-and-coins and Nimstring are PSPACE-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3390719)