Loading...
Please wait, while we are loading the content...
Similar Documents
A Recursive Approach to Solving Parity Games in Quasipolynomial Time
| Content Provider | arXiv |
|---|---|
| Author | Lehtinen, Karoliina Parys, Paweł Schewe, Sven Wojtczak, Dominik |
| Date of Submission | 2022-01-11 |
| Abstract | 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. |
| Related Links | https://arxiv.org/pdf/2104.09717.pdf |
| arXiv | 2104.09717 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computer Science and Game Theory Computer Science - Formal Languages and Automata Theory Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
