Recent results and questions in combinatorial game complexities

DOI10.1016/S0304-3975(00)00062-1zbMATH Open0977.91011WikidataQ126323969 ScholiaQ126323969MaRDI QIDQ1583532FDOQ1583532

Aviezri S. Fraenkel

Publication date: 26 October 2000

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

Recommendations

• scientific article; zbMATH DE number 16390
• Complexity, appeal and challenges of combinatorial games
• scientific article; zbMATH DE number 7075886
• scientific article; zbMATH DE number 2214423
• Games of no chance 3. Papers from the workshop on combinatorial game theory, Banff, Canada, June 2005

zbMATH Keywords

efficiencycomplexitycombinatorial gamestractability

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Games, complexity classes, and approximation algorithms.
• Comparative Study of Approximate Strategies for Playing Sum Games Based on Subgame Types
• Title not available (Why is that?)
• Expository notes on computability and complexity in (arithmetical) games
• Complexity of circuit intersection in graphs
• Title not available (Why is that?)
• The Complexity of Poset Games
• Title not available (Why is that?)

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

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