Automatizability and simple stochastic games

DOI10.1007/978-3-642-22006-7_51MaRDI QIDQ3012836zbMATH OpenOpenAlexFDO

Authors Lei Huang, Toniann Pitassi

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22006-7_51

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15)

Recommendations

• Solving Simple Stochastic Games
• On strategy improvement algorithms for simple stochastic games
• On strategy improvement algorithms for simple stochastic games
• The complexity of stochastic games
• New algorithms for solving simple stochastic games

Cites work

• A subexponential randomized algorithm for the simple stochastic game problem
• Automatizability and simple stochastic games
• Combinatorial structure and randomized subexponential algorithms for infinite games
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• Mean-payoff games and propositional proofs
• New algorithms for solving simple stochastic games
• On Interpolation and Automatization for Frege Systems
• On the automatizability of resolution and related propositional proof systems
• Optimality of size-degree tradeoffs for polynomial calculus
• Optimality of size-width tradeoffs for resolution
• Resolution Is Not Automatizable Unless W[P] Is Tractable
• Settling the complexity of computing two-player Nash equilibria
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Stochastic Games
• The complexity of computing a Nash equilibrium
• The complexity of solving stochastic games on graphs
• The complexity of stochastic games

Cited in

(6)

• The canonical pairs of bounded depth Frege systems
• Automatizability and simple stochastic games
• Parity Games and Propositional Proofs
• Quantum automating TC^0-Frege is LWE-hard
• Quantum automating \(\mathrm{TC}^0\)-Frege is LWE-hard
• Mean-payoff games and propositional proofs

This page was built for publication: Automatizability and simple stochastic games

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