Papex

Open problem · Computer science · Open

Solving parity games

Can the winner of a parity game, played by moving a token on a coloured graph, be determined in polynomial time?

Summary

Parity games are the algorithmic core of automated verification and controller synthesis. Deciding the winner lies in NP and co-NP and has quasi-polynomial-time algorithms, but no polynomial-time algorithm is known.

Why it is open

In a parity game every vertex of a finite directed graph belongs to one of two players, Even and Odd, and the vertices or edges carry positive integer priorities [7, 10]. The owner of the current vertex chooses an outgoing edge, and the play goes on forever; Even wins if the highest priority that occurs infinitely many times is even, and otherwise Odd wins [10]. The algorithmic problem is to decide, for a given game and starting vertex, whether Even has a winning strategy [10].

Parity games are positionally determined: from every starting vertex exactly one player has a winning strategy, and that player can win by always choosing the same edge at each of her vertices, whatever happened before [10]. An important corollary, shown by E. Allen Emerson, Charanjit Jutla and A. Prasad Sistla in 1993, is that deciding the winner is in both NP and co-NP [3, 7, 10]. For this reason the problem is considered unlikely to be NP-complete [2]; why membership in both classes points that way is discussed on the Papex page NP versus co-NP. Many researchers, among them Emerson and Jutla in 1991, asked whether the winner can be determined in polynomial time [7], and Wojciech Czerwiński and colleagues call this "a long-standing open question" [10].

The question matters beyond games. Deciding the winner is polynomial-time equivalent to model checking in the modal μ-calculus, a logic for specifying properties of finite-state systems [2], and to checking emptiness of automata on infinite trees with parity acceptance conditions; it is also at the heart of algorithmic solutions to Church's synthesis problem [10]. In reactive synthesis, for example, formulas of linear temporal logic are translated into automata that are determinised into parity automata, and conditions on these are evaluated by solving the corresponding parity games [7].

A resolution would be a polynomial-time algorithm or a proof that none exists. No prize or committee sets the bar; the status here follows Wikipedia's list of unsolved problems in computer science [14].

What is known

Complexity classes (1991–1998). Emerson and Jutla showed in 1991 that the propositional μ-calculus has the same expressive power as finite automata on infinite trees, and showed how it can be used to establish the determinacy of certain infinite games [1]. From the results of Emerson, Jutla and Sistla, deciding the winner of a parity game is equivalent under linear-time reductions to modal μ-calculus model checking [2, 3]. In 1998 Marcin Jurdziński gave a polynomial-time reduction from parity games to mean-payoff games and observed that deciding mean-payoff games is in UP ∩ co-UP, so parity games are in UP ∩ co-UP as well [2]. UP is the class of problems with unique short certificates that can be checked in polynomial time, and P ⊆ UP ∩ co-UP ⊆ NP ∩ co-NP [2].

Exponential and subexponential algorithms (1993–2011). Robert McNaughton's algorithm decides the winner in time n^(m+O(1)) for n vertices and maximum priority m, later improved to n^(m/2+O(1)) and n^(m/3+O(1)) [7]. Wieslaw Zielonka's recursive algorithm takes exponential time on a family of games of linear size, Oliver Friedmann showed in 2011 [6], yet Jurdziński, Rémi Morvan and K. S. Thejaswini write that it "consistently outperforms most other algorithms in practice" [13]. In 2008 Jurdziński, Mike Paterson and Uri Zwick gave a deterministic subexponential algorithm using polynomial space [4], with running time about n^(O(√n)) [7]. In 2009 Friedmann described a family of games on which the discrete strategy improvement algorithm of Jens Vöge and Jurdziński needs exponentially many strategy iterations, answering in the negative the long-standing question whether it runs in polynomial time [5]. Friedmann's examples were later adapted to prove exponential lower bounds for policy iteration in Markov decision processes and subexponential ones for natural randomised pivoting rules of the simplex method for linear programming [10].

Quasi-polynomial time (2017–2022). In 2017 Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan gave the first quasi-polynomial-time algorithm [10]. It runs in time O(n^(⌈log m⌉+6)) for m priorities, a quasi-polynomial bound because m can always be taken to be at most n, and in time O(n^5) when m is less than log n, so the problem is fixed-parameter tractable in m [7]. Their algorithm uses quasi-polynomial space [7]; Jurdziński and Ranko Lazić reduced the space to nearly linear with succinct progress measures [8], and John Fearnley and colleagues also gave a space-efficient algorithm [10]. Karoliina Lehtinen introduced the register-index, a measure of the complexity of the priority assignment, gave a quasi-polynomial algorithm based on it and showed that games of bounded register-index can be solved in polynomial time [9]. In 2019 Paweł Parys showed that a small modification of Zielonka's algorithm runs in at most quasi-polynomial time [11]. A 2022 journal paper by Lehtinen, Parys, Sven Schewe and Dominik Wojtczak combines this with a preprint of Lehtinen, Schewe and Wojtczak and describes two such recursive algorithms, with complexity n^(O(log(1+d/log n))) for d priorities [12, 13]. Jurdziński, Morvan and Thejaswini generalised these into a universal attractor decomposition algorithm, in which an attractor is the largest set of vertices from which a player can force the play into a given target set [13].

Lower bounds for families of algorithms (2019–2022). Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Jurdziński, Lazić and Parys argued in 2019 that the existing quasi-polynomial techniques (the play summaries of Calude and colleagues, progress measures and register games) are all instances of a separation approach [10]. Each builds, explicitly or implicitly, an automaton that separates plays decisively won by one player from plays won by the other, which reduces the parity game to a safety game, where one player only has to avoid a set of unsafe vertices [10]. They proved that every such separating safety automaton has at least a quasi-polynomial number of states, a bound that nearly matches the best upper bounds and forms "a barrier that all existing approaches must overcome" [10]. The central object is a universal ordered tree; its smallest size is quasi-polynomial, so progress-measure algorithms cannot become sub-quasi-polynomial by finding smaller trees [10]. In 2022 Jurdziński, Morvan and Thejaswini showed that the Lehtinen–Schewe–Wojtczak algorithm, and non-adaptive versions of the McNaughton–Zielonka and Parys algorithms, arise from their universal algorithm run on specific universal trees [13].

Main approaches

Separating automata and universal trees. Reduce the parity game to a safety game through a separating automaton, or search a universal tree for a progress measure that witnesses a winning strategy [10]. Strongest evidence: every quasi-polynomial technique known when the paper was written in 2018 fits this scheme [10], and its space needs have been brought down to nearly linear [8]. Main difficulty: the quasi-polynomial lower bound on separating safety automata and universal trees [10].

Attractor decomposition. Split the game recursively into attractors and smaller subgames, as the McNaughton–Zielonka algorithm does [13]. Strongest evidence: the classic algorithm was the most useful in a practical comparison by Friedmann and Martin Lange [7] and remains hard to beat in practice [13]; its modifications reach quasi-polynomial time [11, 12]. Main difficulty: the classic algorithm is exponential in the worst case [6], and the Lehtinen–Schewe–Wojtczak algorithm and non-adaptive versions of the others run on universal trees [13], whose size has a quasi-polynomial lower bound [10].

Strategy improvement, simplex-style methods and quantitative games. Use strategy improvement or methods derived from the simplex algorithm, or solve the game through mean-payoff, discounted or simple stochastic games, to which parity games reduce [2, 4, 5, 10]. Strongest evidence: the reduction to mean-payoff games gives membership in UP ∩ co-UP [2], and the fastest algorithms known before 2008, randomised and subexponential, were based on subexponential simplex algorithms [4]. Main difficulty: Friedmann's games force exponentially many iterations of the Vöge–Jurdziński algorithm, and of Schewe's variant [5]; the quantitative games are no easier than parity games [10].

Parameters and structure. Find measures that make the problem easy when they are small [7, 9]. Strongest evidence: fixed-parameter tractability in the number of priorities [7] and polynomial time for bounded register-index [9]. Main difficulty: with up to n priorities the bound of Calude and colleagues is only quasi-polynomial [7].

Open sub-questions

  1. Adaptive attractor algorithms. Jurdziński, Morvan and Thejaswini obtain only non-adaptive versions of the McNaughton–Zielonka and Parys algorithms from universal trees. Do the adaptive versions also need quasi-polynomial time in the worst case [10, 13]?
  2. Beyond separation. Is there a sub-quasi-polynomial algorithm that does not reduce the game to a safety game through a separating automaton, the setting of Czerwiński et al.'s lower bound [10]?
  3. Strategy improvement. Is there an improvement rule that needs only polynomially many iterations on every parity game, given that Friedmann's games defeat the Vöge–Jurdziński rule and Schewe's variant [5]?
  4. Register-index in synthesis. For parity games produced from linear temporal logic specifications in reactive synthesis, is the register-index bounded by a small constant, so that Lehtinen's algorithm runs in polynomial time on them [7, 9]?
  5. Fast in practice and in theory. Can a quasi-polynomial variant of Zielonka's algorithm match the classic algorithm on typical inputs while keeping its worst-case bound, as Parys hoped in 2019 [7, 11]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Emerson, E. A. & Jutla, C. S. (1991). Tree automata, mu-calculus and determinacy. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), IEEE, 368–377. 10.1109/SFCS.1991.185392 · Checked 16 Oct 2026
  2. Jurdziński, M. (1998). Deciding the winner in parity games is in UP ∩ co-UP. Information Processing Letters 68(3), 119–124. 10.1016/S0020-0190(98)00150-1 · Checked 16 Oct 2026
  3. Emerson, E. A., Jutla, C. S. & Sistla, A. P. (2001). On model checking for the μ-calculus and its fragments. Theoretical Computer Science 258(1–2), 491–522; conference version in CAV 1993. 10.1016/S0304-3975(00)00034-7 · Checked 16 Oct 2026
  4. Jurdziński, M., Paterson, M. & Zwick, U. (2008). A deterministic subexponential algorithm for solving parity games. SIAM Journal on Computing 38(4), 1519–1532. 10.1137/070686652 · Checked 16 Oct 2026
  5. Friedmann, O. (2009). An exponential lower bound for the parity game strategy improvement algorithm as we know it. In 24th Annual IEEE Symposium on Logic in Computer Science (LICS 2009), 145–156. 10.1109/LICS.2009.27 · Checked 16 Oct 2026
  6. Friedmann, O. (2011). Recursive algorithm for parity games requires exponential time. RAIRO – Theoretical Informatics and Applications 45(4), 449–457. 10.1051/ita/2011124 · Checked 16 Oct 2026
  7. Calude, C. S., Jain, S., Khoussainov, B., Li, W. & Stephan, F. (2017). Deciding parity games in quasipolynomial time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), 252–263; journal version in SIAM Journal on Computing 51(2), STOC17-152–STOC17-188 (2022; published online 2020), DOI 10.1137/17M1145288. 10.1145/3055399.3055409 · Checked 16 Oct 2026
  8. Jurdziński, M. & Lazić, R. (2017). Succinct progress measures for solving parity games. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 1–9. 10.1109/LICS.2017.8005092 · Checked 16 Oct 2026
  9. Lehtinen, K. (2018). A modal μ perspective on solving parity games in quasi-polynomial time. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), 639–648. 10.1145/3209108.3209115 · Checked 16 Oct 2026
  10. Czerwiński, W., Daviaud, L., Fijalkow, N., Jurdziński, M., Lazić, R. & Parys, P. (2019). Universal trees grow inside separating automata: quasi-polynomial lower bounds for parity games. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), 2333–2349. 10.1137/1.9781611975482.142 · Checked 16 Oct 2026
  11. Parys, P. (2019). Parity games: Zielonka's algorithm in quasi-polynomial time. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Leibniz International Proceedings in Informatics 138, 10:1–10:13. 10.4230/LIPIcs.MFCS.2019.10 · Checked 16 Oct 2026
  12. Lehtinen, K., Parys, P., Schewe, S. & Wojtczak, D. (2022). A recursive approach to solving parity games in quasipolynomial time. Logical Methods in Computer Science 18(1), 8. 10.46298/lmcs-18(1:8)2022 · Checked 16 Oct 2026
  13. Jurdziński, M., Morvan, R. & Thejaswini, K. S. (2022). Universal algorithms for parity games and nested fixpoints. In Principles of Systems Design, Lecture Notes in Computer Science 13660, Springer, 252–271. 10.1007/978-3-031-22337-2_12 · Checked 16 Oct 2026
  14. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing