Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?

up vote 6 down vote accepted

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.

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.