[Solved]: Is it possible to solve parity game problem in polynomial time?

Problem Detail: 

Is it practically possible or even near possible to make parity game to be solved in polynomial time? If yes, how? and if No, why?

Asked By : Andy

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16399