patternMinor
Solve parity game in polynomial time?
Viewed 0 times
polynomialparitytimegamesolve
Problem
Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?
Solution
The state of the art for solving parity games is now quasipolynomial time. Here are references:
Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.
A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.
Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić, LICS 2017.
An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak
Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.
A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.
Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić, LICS 2017.
An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak
Context
StackExchange Computer Science Q#16399, answer score: 8
Revisions (0)
No revisions yet.