Recursive algorithm for parity games requires exponential time
Oliver Friedmann · RAIRO - Theoretical Informatics and Applications · 2011
This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.