GO Is Polynomial-Space Hard
From MaRDI portal
Publication:3873542
DOI10.1145/322186.322201zbMath0434.68028OpenAlexW2156827107WikidataQ29040218 ScholiaQ29040218MaRDI QIDQ3873542
Michael Sipser, David Lichtenstein
Publication date: 1980
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322186.322201
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Computing methodologies and applications (68U99)
Related Items
On the computational complexities of various geography variants, Complexity, appeal and challenges of combinatorial games, On variants of vertex geography on undirected graphs, PSPACE-Hardness of some combinatorial games, Single-suit two-person card play, On the complexity of connection games, The game chromatic number and the game colouring number of cactuses, On the number of go positions on lattice graphs, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, The shortest connection game, On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games, \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\), UNO is hard, even for a single player, Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game, Havannah and TwixT are PSPACE-complete, Phutball is PSPACE-hard, Single-Player and Two-Player Buttons & Scissors Games, Storage allocation is NP-hard, Bichromatic coloring game on triangulations, On the complexity of computational problems associated with simple stochastic games, Feedback game on \(3\)-chromatic Eulerian triangulations of surfaces, Computing a perfect strategy for nxn chess requires time exponential in n, Playing disjunctive sums is polynomial space complete, Unnamed Item, Unnamed Item, Theory of annihilation games. I, The Go polynomials of a graph., New complexity results about Nash equilibria, On the fairness and complexity of generalized \(k\)-in-a-row games, A finite set of functions with an EXPTIME-complete composition problem, Remarks on History and Presence of Game Tree Search and Research, Hanabi is NP-hard, even for cheaters who look at their cards, THE FRONTIER OF DECIDABILITY IN PARTIALLY OBSERVABLE RECURSIVE GAMES, Undirected edge geography, Geography, Complexity of path-forming games, TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable, The one-round Voronoi game replayed, PSPACE-completeness of an escape problem, An algorithmic analysis of the Honey-Bee game, Lower bounds for multiplayer noncooperative games of incomplete information, Computer Go, Computer Go: An AI oriented survey, On the shortest path game, Turing machines with access to history, Recent results and questions in combinatorial game complexities, Applying adversarial planning techniques to Go, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete., The complexity of two-player games of incomplete information, The Othello game on an \(n\times n\) board is PSPACE-complete, Decision algorithms for multiplayer noncooperative games of incomplete information, Rikudo is NP-complete, Learning to score final positions in the game of Go
