Provably Difficult Combinatorial Games
From MaRDI portal
Publication:3854623
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
diagonalizationpropositional formulasdecision problemperfect informationcombinatorial gamepolynomial-time reducibilitycompleteness in exponential timemoving markers on a graph
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
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
