一句话：提出 Zielonka 递归算法的改进，将奇偶博弈求解复杂度降至拟多项式时间。
奇偶博弈（parity games）求解是形式验证与自动机理论中的核心问题。经典的 Zielonka 递归算法结构简单，但最坏时间复杂度为指数级；现有最优算法虽已达到拟多项式时间，却通常更为复杂。本文对 Zielonka 经典算法进行修改，在保留递归方法简洁性的同时降低其复杂度。作者通过复杂度分析证明，对于规模为 n、优先数为 d 的奇偶博弈，该算法的时间复杂度为 n^{O(log(1+d/log n))}，与已有拟多项式时间算法一致。这一结果表明，经典递归方法经过适当调整同样可以达到当前最优的渐近上界。
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of Zielonka's classic algorithm that brings its complexity down to $n^{O\left(\log\left(1+\frac{d}{\log n}\right)\right)}$, for parity games of size $n$ with $d$ priorities, in line with previous quasipolynomial-time solutions.
@article{paperbot1749,
title = {A Recursive Approach to Solving Parity Games in Quasipolynomial Time},
author = {Karoliina Lehtinen and Paweł Parys and Sven Schewe and Dominik Wojtczak},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:8)2022}
}