Automatizability and Simple Stochastic Games

DOI10.1007/978-3-642-22006-7_51zbMath1334.68100OpenAlexW2143451091MaRDI QIDQ3012836

Toniann Pitassi, Lei Huang

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

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

Related Items (3)

Parity Games and Propositional Proofs ⋮ The canonical pairs of bounded depth Frege systems ⋮ Automatizability and Simple Stochastic Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial structure and randomized subexponential algorithms for infinite games
• The complexity of stochastic games
• Optimality of size-width tradeoffs for resolution
• On the automatizability of resolution and related propositional proof systems
• A subexponential randomized algorithm for the simple stochastic game problem
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Optimality of size-degree tradeoffs for polynomial calculus
• Automatizability and Simple Stochastic Games
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• Settling the complexity of computing two-player Nash equilibria
• Mean-Payoff Games and Propositional Proofs
• The Complexity of Solving Stochastic Games on Graphs
• On Interpolation and Automatization for Frege Systems
• The Complexity of Computing a Nash Equilibrium
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Stochastic Games

This page was built for publication: Automatizability and Simple Stochastic Games