\textsf{PSPACE}-completeness of k-\textsc{Atropos}

DOI10.1016/J.DAM.2025.03.010MaRDI QIDQ6995817zbMATH OpenFDO

Authors Chao Yang, Zhujun Zhang

Publication date 17 April 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.03.010

zbMATH Keywords

\textsc{Atropos}\textsf{PSPACE}-completecombinatorial gamescomputational complexitytrue quantified Boolean formula (TQBF)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Combinatorial games (91A46)

Cites work

• N by N Checkers is Exptime Complete
• Atropos: a PSPACE-complete Sperner triangle game
• Combinatorial game theory
• Computing a perfect strategy for nxn chess requires time exponential in n
• Games, puzzles, and computation
• GO Is Polynomial-Space Hard
• Gobang is PSPACE-complete
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• scientific article; zbMATH DE number 1759687 (Why is no real title available?)
• The Othello game on an \(n\times n\) board is PSPACE-complete

This page was built for publication: \textsf{PSPACE}-completeness of \(k\)-\textsc{Atropos}

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