Provably Difficult Combinatorial Games

DOI10.1137/0208013MaRDI QIDQ3854623zbMATH OpenOpenAlexFDO

Authors Ashok K. Chandra, Larry J. Stockmeyer

Publication date 1979

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0208013

zbMATH Keywords

combinatorial gamecompleteness in exponential timedecision problemdiagonalizationmoving markers on a graphperfect informationpolynomial-time reducibilitypropositional formulas

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05)

Cited in

(41)

• Deciding inseparability and conservative extensions in the description logic
• Solitaire automata
• Alternating tree automata
• Single-suit two-person card play
• Alternating multihead finite automata
• Tree-size bounded alternation
• The complexity of problems in systems of communicating sequential processes
• Computing a perfect strategy for nxn chess requires time exponential in n
• Theory of annihilation games. I
• Complexity of path-forming games
• Almost every set in exponential time is P-bi-immune
• Complexity of path discovery game problems
• Decision algorithms for multiplayer noncooperative games of incomplete information
• Imperfect information in reactive modules games
• Model-checking iterated games
• Domino-tiling games
• Complexity, appeal and challenges of combinatorial games
• Weakly complete problems are not rare
• Backgammon is hard
• QUIXO is EXPTIME-complete
• Cops and robbers is EXPTIME-complete
• The computational complexity of Angry Birds
• From model checking to equilibrium checking: reactive modules for rational verification
• Mean-payoff games with \(\omega\)-regular specifications
• The complexity of searching implicit graphs
• The complexity of synchronous notions of information flow security
• The Complexity of Escaping Labyrinths and Enchanted Forests.
• A Temporal Logic of Normative Systems
• Classifying the computational complexity of problems
• The guarding game is E-complete
• The complexity of searching succinctly represented graphs
• Fine-grained Lower Bounds on Cops and Robbers
• scientific article; zbMATH DE number 7455737 (Why is no real title available?)
• scientific article; zbMATH DE number 7278100 (Why is no real title available?)
• Petri games: synthesis of distributed systems with causal memory
• Computing the width of non-deterministic automata
• Lower bounds for multiplayer noncooperative games of incomplete information
• Extending the description logic \(\mathcal{EL}\) with threshold concepts induced by concept measures
• The complexity of pursuit on a graph
• All paths lead to Rome
• The complexity of two-player games of incomplete information

This page was built for publication: Provably Difficult Combinatorial Games

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