The complexity of two-player games of incomplete information
From MaRDI portal
Publication:800838
DOI10.1016/0022-0000(84)90034-5zbMath0551.90100OpenAlexW2092977061MaRDI QIDQ800838
Publication date: 1984
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(84)90034-5
incomplete informationspace complexityAsymptotically optimal decision algorithmsBlindfold gamesexponential space complete outcome problemsPrivate alternating Turing machinesspace bounded games
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Related Items (52)
What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives ⋮ Quantum alternation ⋮ The complexity of synchronous notions of information flow security ⋮ Lazy Synthesis ⋮ Looking at mean payoff through foggy windows ⋮ An alternating-time temporal logic with knowledge, perfect recall and past: axiomatisation and model-checking ⋮ Minimum Attention Controller Synthesis for Omega-Regular Objectives ⋮ Compositional and symbolic synthesis of reactive controllers for multi-agent systems ⋮ Mean-payoff games with partial observation ⋮ Knowledge-based strategies for multi-agent teams playing against nature ⋮ Polynomial games and determinacy ⋮ Unnamed Item ⋮ Common knowledge and update in finite environments ⋮ Latticed-LTL synthesis in the presence of noisy inputs ⋮ Model-checking games for logics of imperfect information ⋮ Connectivity games over dynamic networks ⋮ Information tracking in games on graphs ⋮ BOCoSy: Small but Powerful Symbolic Output-Feedback Control ⋮ Randomness for free ⋮ Cooperating in video games? Impossible! Undecidability of team multiplayer games ⋮ Classifying the computational complexity of problems ⋮ Symbolic supervisory control of infinite transition systems under partial observation using abstract interpretation ⋮ Observation and distinction: representing information in infinite games ⋮ Strategy construction for parity games with imperfect information ⋮ Unnamed Item ⋮ Game-based Synthesis of Distributed Controllers for Sampled Switched Systems ⋮ Strategy Construction for Parity Games with Imperfect Information ⋮ Indecision and delays are the parents of failure -- taming them algorithmically by synthesizing delay-resilient control ⋮ The complexity of debate checking ⋮ The complexity of pursuit on a graph ⋮ Multi-oracle interactive protocols with constant space verifiers ⋮ A GENERAL NOTION OF UNIFORM STRATEGIES ⋮ Infinite games with finite knowledge gaps ⋮ Feasibility analysis of sporadic real-time multiprocessor task systems ⋮ Partial-Observation Stochastic Games ⋮ Alternating-time stream logic for multi-agent systems ⋮ Unnamed Item ⋮ The complexity of asynchronous model based testing ⋮ Lower bounds for multiplayer noncooperative games of incomplete information ⋮ Computing Weakest Strategies for Safety Games of Imperfect Information ⋮ On Decision Problems for Probabilistic Büchi Automata ⋮ Turing machines with access to history ⋮ A Compositional Framework for Controller Synthesis ⋮ Probabilistic game automata ⋮ THE COMPLEXITY OF COVERAGE ⋮ Solitaire automata ⋮ POMDPs under probabilistic semantics ⋮ Uniform strategies, rational relations and jumping automata ⋮ Time-aware uniformization of winning strategies ⋮ Compositional construction of most general controllers ⋮ Decision algorithms for multiplayer noncooperative games of incomplete information ⋮ Computation of equilibria in noncooperative games
Cites Work
- Unnamed Item
- Unnamed Item
- Space-bounded reducibility among combinatorial problems
- The polynomial-time hierarchy
- On the complexity of some two-person perfect-information games
- Decision algorithms for multiplayer noncooperative games of incomplete information
- Relationships between nondeterministic and deterministic tape complexities
- Provably Difficult Combinatorial Games
- GO Is Polynomial-Space Hard
- Alternation
- A Combinatorial Problem Which Is Complete in Polynomial Space
- On the Computational Complexity of Algorithms
This page was built for publication: The complexity of two-player games of incomplete information
