Recent results and questions in combinatorial game complexities

DOI10.1016/S0304-3975(00)00062-1zbMath0977.91011WikidataQ126323969 ScholiaQ126323969MaRDI QIDQ1583532

Aviezri S. Fraenkel

Publication date: 26 October 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexityefficiencycombinatorial gamestractability

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance (91-02) Complexity and performance of numerical algorithms (65Y20) Combinatorial games (91A46)

Related Items (2)

Complexity of circuit intersection in graphs ⋮ The Complexity of Poset Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of pursuit on a graph
• Misère annihilation games
• A deletion game on hypergraphs
• PSPACE-Hardness of some combinatorial games
• The generalized Sprague-Grundy function and its invariance under certain mappings
• Epidemiography. II: Games with a dozing yet winning player
• Complexity of problems in games, graphs and algebraic equations
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• A complete analysis of von Neumann's Hackendot
• Nonhomogeneous spectra of numbers
• Computing a perfect strategy for nxn chess requires time exponential in n
• Playing disjunctive sums is polynomial space complete
• Theory of annihilation games. I
• Sums of Zuchswang games
• Strategy for a class of games with dynamic ties
• On the complexity of some two-person perfect-information games
• Gobang is PSPACE-complete
• Heap games, numeration systems and sequences
• Constant bounds on the moments of the height of binary search trees
• Nim-type games
• N by N Checkers is Exptime Complete
• Systems of Numeration
• Some combinatorial game problems require Ω( n ^k ) time
• Classes of Pebble Games and Complete Problems
• GO Is Polynomial-Space Hard
• A Curious Nim-Type Game
• Theory of annihilation games
• A Combinatorial Problem Which Is Complete in Polynomial Space
• All Games Bright and Beautiful
• Algebraic solutions of partizan games with cycles
• Loopy Games
• A Gamut of Game Theories
• Strategies for compounds of partizan games
• Graphs and composite games

This page was built for publication: Recent results and questions in combinatorial game complexities