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 $NPcap coNP$, and in fact, in $UPcap 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 $NPcap 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