PSPACE-Hardness of some combinatorial games

DOI10.1016/0097-3165(87)90074-4zbMath0619.90109OpenAlexW2077313418MaRDI QIDQ1090274

Aviezri S. Fraenkel, Elisheva Goldschmidt

Publication date: 1987

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(87)90074-4

zbMATH Keywords

annihilationcombinatorial gamesPSPACE-completenessimpartial gamesblocking, capturegames on digraphspartizan gamesPSPACE-hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20) Positional games (pursuit and evasion, etc.) (91A24)

Related Items (10)

Traveling salesmen in the presence of competition ⋮ Complexity, appeal and challenges of combinatorial games ⋮ The complexity of node blocking for dags ⋮ The complexity of pursuit on a graph ⋮ The complexity of coloring games on perfect graphs ⋮ Undirected edge geography ⋮ Complexity of path-forming games ⋮ Unnamed Item ⋮ On the shortest path game ⋮ Recent results and questions in combinatorial game complexities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of problems in games, graphs and algebraic equations
• A complete analysis of von Neumann's Hackendot
• Theory of annihilation games. I
• On the complexity of some two-person perfect-information games
• GO Is Polynomial-Space Hard
• A Combinatorial Problem Which Is Complete in Polynomial Space

This page was built for publication: PSPACE-Hardness of some combinatorial games