Phutball is PSPACE-hard

DOI10.1016/j.tcs.2010.08.019zbMath1235.91034OpenAlexW2141292420WikidataQ56059185 ScholiaQ56059185MaRDI QIDQ410721

Dariusz Dereniowski

Publication date: 3 April 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.019

zbMATH Keywords

computational complexitygamesphutballPSPACE hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial games (91A46)

Cites Work

• On the complexity of some two-person perfect-information games
• The Othello game on an \(n\times n\) board is PSPACE-complete
• N by N Checkers is Exptime Complete
• GO Is Polynomial-Space Hard
• A Combinatorial Problem Which Is Complete in Polynomial Space
• Minesweeper is NP-complete.
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Phutball is PSPACE-hard