Hex ist Pspace-vollständig. (Hex is Pspace-complete)
From MaRDI portal
Publication:1138494
DOI10.1007/BF00288964zbMath0431.90103OpenAlexW1574089563WikidataQ55951220 ScholiaQ55951220MaRDI QIDQ1138494
Publication date: 1981
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00288964
computational complexitygames on graphsHexcombinatorial two-person gamesparticular gamePspace-complete decision problemPspace-hard problems
Related Items
On the complexity of connection games, Backgammon is hard, Topological games at Princeton, a mathematical memoir, \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\), Havannah and TwixT are PSPACE-complete, The maker-breaker largest connected subgraph game, Classifying the computational complexity of problems, Hex and combinatorics, QUIXO is EXPTIME-complete, Computing a perfect strategy for nxn chess requires time exponential in n, Unnamed Item, Theory of annihilation games. I, A difficulty in particular Shannon-like games, Shannon-like games are difficult, Remarks on History and Presence of Game Tree Search and Research, The complexity of coloring games on perfect graphs, On the combinatorial value of Hex positions, Geography, TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable, An algorithmic analysis of the Honey-Bee game, A hierarchical approach to computer Hex, Games solved: Now and in the future, The largest connected subgraph game, The largest connected subgraph game, Recent results and questions in combinatorial game complexities, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete., The Othello game on an \(n\times n\) board is PSPACE-complete, Rikudo is NP-complete, Solving \(7\times 7\) hex with domination, fill-in, and virtual connections
Cites Work
