GO Is Polynomial-Space Hard
- 1 April 1980
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 27 (2), 393-401
- https://doi.org/10.1145/322186.322201
Abstract
It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is proved that GO is Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and finally to GO.Keywords
This publication has 4 references indexed in Scilit:
- GO is pspace hardPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- The complexity of checkers on an N × N boardPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- On the complexity of some two-person perfect-information gamesJournal of Computer and System Sciences, 1978
- A Combinatorial Problem Which Is Complete in Polynomial SpaceJournal of the ACM, 1976