Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Parity games are famously known to be in $NP\cap coNP$, and in fact, in $UP\cap coUP$. However, there are no polynomial algorithms known for them.
To be more specific, the best algorithms run in time that is polynomial in the number of states $n$, but exponential in the parity index $d$.
The state of the art, as far as I know, is Jurdzinsky's work here.
Parity games is one of the rare problems we know to be in $NP\cap coNP$, but don't know to be in $P$. Since most other candidates for such languages were eventually shown to be in $P$, it is not unreasonable to believe that a polynomial time algorithm will be found.
$\begingroup$
$\endgroup$
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
