Computational complexity of generalized Push Fight

DOI10.4230/LIPICS.FUN.2018.11MaRDI QIDQ3305729zbMATH OpenFDO

Authors Jeffrey Bosboom, Erik D. Demaine, Mikhail Rudoy

Publication date 11 August 2020

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

zbMATH Keywords

board gameshardnessmate-in-one

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorial games (91A46)

Recommendations

• Phutball is PSPACE-hard
• On the computational complexities of various geography variants
• PSPACE-Hardness of some combinatorial games
• The Othello game on an \(n\times n\) board is PSPACE-complete
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete

Cites work

• N by N Checkers is Exptime Complete
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1944408 (Why is no real title available?)
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(7)

• Single-player and two-player buttons \& scissors games (extended abstract)
• On the PSPACE-completeness of Peg Duotaire and other peg-jumping games
• Phutball is PSPACE-hard
• Directional phutball
• Magic: The Gathering is Turing complete
• The computational complexity of Evil Hangman
• Generalized Pete's Pike is PSPACE-complete

This page was built for publication: Computational complexity of generalized Push Fight

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