David Lichtenstein
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.
- 1 BERLEKAMP, E R, CONWAY, J, AND GUY, R Wmmng Ways Academic Press, New York. To appearGoogle Scholar
- 2 BLOCK, H C Axioms for GO SIGART Newsletter (ACM), 51 (Aprd 1975), p 13Google Scholar
- 3 CHANDRA, A K, AND STOCKMEYER, L J Alternation 17th Annual IEEE Symp Found Comptr So, Houston, Texas, 1973, pp 98-108Google Scholar
- 4 EVEN, S, AND TAR JAN, R E A combmatonal problem whtch is complete in polynomial space J A CM 23. 4 (Oct 1976), 710--719 Google Scholar
- 5 FRAENKEL, A S, GAREY, M R, JOHNSON, D.S, SCHAEFER, T J, AND YESHA, Y. The complexity of checkers on an n x n board 19th Annual IEEE Symp Found Comptr Scl, Ann Arbor, MJch, 1978, pp 55-64Google Scholar
- 6 KARP, P M Reduoblhty among combinatorial problems In Complexny of Computer Computanons, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972Google Scholar
- 7 LICHTENSTEIN, D Planar formulae and their uses. To appear m SlAM J ComptgGoogle Scholar
- 8 LICHTENSTEIN, D, AND SIPSER, M GO is Pspace Hard. Memo No UCB/ERL M78/16, Electronics Res Lab., U of Cahfornla, Berkeley Cahf 1978.Google Scholar
- 9 MEYER, A R, AND STOCKMEYER, L J Word problems requiring exponenual t~me Preliminary Report Proc 5th Annual ACM Symp Theory Comptg, Austin, Texas, 1973, pp 1-9 Google Scholar
- 10 SCHAEFER, T J On the complexity of some two-person perfect-mformauon games. Z Comptr Syst Scz 16, 2 (April 1978), 185-225Google Scholar
Index Terms
- GO Is Polynomial-Space Hard
Recommendations
GO-Mapper: functional analysis of gene expression data using the expression level as a score to evaluate Gene Ontology terms
Motivation: Retrieval of information on biological processes from large-scale expression data is still a time-consuming task. An automated analysis utilizing all expression information would greatly increase our understanding of the samples under ...
A graph-theoretic modeling on GO space for biological interpretation of gene clusters
Motivation: With the advent of DNA microarray technologies, the parallel quantification of genome-wide transcriptions has been a great opportunity to systematically understand the complicated biological phenomena. Amidst the enthusiastic investigations ...
GO: :TermFinder---open source software for accessing Gene Ontology information and finding significantly enriched Gene Ontology terms associated with a list of genes
Summary: GO::TermFinder comprises a set of object-oriented Perl modules for accessing Gene Ontology (GO) information and evaluating and visualizing the collective annotation of a list of genes to GO terms. It can be used to draw conclusions from ...
Comments