Attractors Is All You Need: Parity Games In Polynomial Time
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918187975573504 |
|---|---|
| author | van der Heijden, Rick |
| author_facet | van der Heijden, Rick |
| contents | 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 attractor-based algorithms, the presented algorithm only removes regions with a determined winner. The paper introduces a new type of attractor that can guarantee finding the minimal dominion of a parity game. The attractor runs in polynomial time and can peel the graph empty. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03752 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Attractors Is All You Need: Parity Games In Polynomial Time van der Heijden, Rick Data Structures and Algorithms Computational Complexity Formal Languages and Automata Theory Computer Science and Game Theory Logic in Computer Science 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 attractor-based algorithms, the presented algorithm only removes regions with a determined winner. The paper introduces a new type of attractor that can guarantee finding the minimal dominion of a parity game. The attractor runs in polynomial time and can peel the graph empty. |
| title | Attractors Is All You Need: Parity Games In Polynomial Time |
| topic | Data Structures and Algorithms Computational Complexity Formal Languages and Automata Theory Computer Science and Game Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2511.03752 |