Game values and computational complexity: an analysis via black-white combinatorial games

DOI10.1007/978-3-662-48971-0_58MaRDI QIDQ3459906zbMATH OpenOpenAlexFDO

Authors Daniel Grier, Jochen Messner, Luke Schaeffer, S. Fenner, Thomas Thierauf

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48971-0_58

zbMATH Keywords

black-white gamesColcombinatorial gamescomputational complexityGraph Nimnumeric gamesposet games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Combinatorial games (91A46)

Recommendations

• scientific article; zbMATH DE number 7075886
• PSPACE-Hardness of some combinatorial games
• Pomax games -- a family of integer-valued partizan games played on posets
• The complexity of poset games
• On the computational complexities of various geography variants

Cited in

(7)

• \textsf{PSPACE}-complete two-color planar placement games
• ON THE COMPLEXITY OF COMPUTING VALUES OF RESTRICTED GAMES
• The computational complexity of forced capture Hnefatafl
• Bounded degree QBF and positional games
• 6-uniform maker-breaker game is PSPACE-complete
• The Avoider-Enforcer game in hypergraphs of rank 3
• On the algorithmic complexity of the Mastermind game with black-peg results

This page was built for publication: Game values and computational complexity: an analysis via black-white combinatorial games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459906)