Attractors Is All You Need: Parity Games In Polynomial Time

Rick van der Heijden

This paper provides a polynomial-time algorithm for solving parity games that runs in $\mathcal{O}(n^2\cdot (n+m))$ time-ending a search that has taken decades. Unlike previous…