Provably Difficult Combinatorial Games

DOI10.1137/0208013zbMath0421.68044OpenAlexW1983796355MaRDI QIDQ3854623

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

diagonalizationpropositional formulasdecision problemperfect informationcombinatorial gamepolynomial-time reducibilitycompleteness in exponential timemoving markers on a graph

Mathematics Subject Classification ID

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

Related Items (40)

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

This page was built for publication: Provably Difficult Combinatorial Games