A superpolynomial lower bound for strategy iteration based on snare memorization

DOI10.1016/j.dam.2013.02.007zbMath1296.68067OpenAlexW2071453765MaRDI QIDQ2446310

Oliver Friedmann

Publication date: 16 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.02.007

zbMATH Keywords

parity gameslower boundsstrategy iteration

Mathematics Subject Classification ID

Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Symmetric Strategy Improvement ⋮ Robust worst cases for parity games algorithms ⋮ Unnamed Item ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• The complexity of stochastic games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• The complexity of mean payoff games on graphs
• Automata, logics, and infinite games. A guide to current research
• Non-oblivious Strategy Improvement
• An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• A deterministic subexponential algorithm for solving parity games
• Solving Parity Games in Big Steps
• On Nonterminating Stochastic Games
• On model checking for the \(\mu\)-calculus and its fragments

This page was built for publication: A superpolynomial lower bound for strategy iteration based on snare memorization