A PSPACE-complete graph nim

MaRDI QIDQ3295616zbMATH OpenFDO

Authors Kyle Burke, Olivia C. Geore

Publication date 10 July 2020

zbMATH Keywords

combinatorial game theorygraph nimimpartial gamesneighboring nimnim

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Combinatorial games (91A46) Algorithmic game theory and complexity (91A68)

Recommendations

• On the complexity of the misère version of three games played on graphs
• Strings-and-coins and Nimstring are PSPACE-complete
• A Nim game played on graphs. II.
• Strings-and-coins and nimstring are PSPACE-complete
• PSPACE-Hardness of some combinatorial games

Cited in

(9)

• PSPACE-Hardness of some combinatorial games
• On the complexity of the misère version of three games played on graphs
• Strings-and-coins and Nimstring are PSPACE-complete
• Vertex Nim played on graphs
• Strings-and-coins and nimstring are PSPACE-complete
• Nimber-preserving reduction: game secrets and homomorphic Sprague-Grundy theorem
• Topological network-control games
• Topological network-control games played on graphs
• Network control games played on graphs

This page was built for publication: A PSPACE-complete graph nim

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