On the complexity of computational problems associated with simple stochastic games

DOI10.1007/3-540-61332-3_165zbMath1529.68121OpenAlexW2111319113MaRDI QIDQ6184676

Akio Yanbe, Kouichi Sakurai

Publication date: 29 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61332-3_165

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15)

Cites Work

• Unnamed Item
• Unnamed Item
• Games against nature
• Computing a perfect strategy for nxn chess requires time exponential in n
• Positional strategies for mean payoff games
• The complexity of short two-person games
• The complexity of stochastic games
• Complete problems for deterministic polynomial time
• Discounted Markov games: Generalized policy iteration method
• Discounted Markov games; successive approximation and stopping times
• On the complexity of some two-person perfect-information games
• A note on the graph isomorphism counting problem
• A short certificate of the number of universal optimal strategies for stopping simple stochastic games
• Probabilistic game automata
• A subexponential randomized algorithm for the simple stochastic game problem
• Algorithms for discounted stochastic games
• N by N Checkers is Exptime Complete
• Nonlinear programming and stationary strategies in stochastic games
• The Complexity of Markov Decision Processes
• The Complexity of Enumeration and Reliability Problems
• GO Is Polynomial-Space Hard
• A Monte-Carlo Algorithm for Estimating the Permanent
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Every Prime Has a Succinct Certificate
• A Combinatorial Problem Which Is Complete in Polynomial Space
• On Nonterminating Stochastic Games
• Stochastic Games

This page was built for publication: On the complexity of computational problems associated with simple stochastic games