Parity games are conceptually easy to understand and might just be solvable in polynomial time! So far, no polynomial time solution has been discovered. Surely this fact attracts the attention of algorithm aficionados. Quasi-polynomial time solutions have been found in the recent decade, along with proofs that certain families of parity game algorithms have a quasi-polynomial time lower bound. Since parity games are in the intersection of NP and co-NP, even UP and co-UP, surely they admit a polynomial-time solution? The quest is therefore not finished, the question remains open: can we solve parity games in polynomial time? Or can we not, and would that imply that parity games separate P and NP? We focus our attention on algorithms that repeatedly partition parity games using attractors, extended with knowledge of tangles. Tangles are subgames that are won by one player, forcing the other player to escape the tangle. By repeatedly partitioning the game and obtaining new tangles from the partition, tangle learning algorithms solve parity games. Our journey so far has focused on designing various variations of tangle learning and subsequently exploring examples that maximally distract and delay these tangle learning variations.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving Parity Games, Very Slowly

  • Tom van Dijk

摘要

Parity games are conceptually easy to understand and might just be solvable in polynomial time! So far, no polynomial time solution has been discovered. Surely this fact attracts the attention of algorithm aficionados. Quasi-polynomial time solutions have been found in the recent decade, along with proofs that certain families of parity game algorithms have a quasi-polynomial time lower bound. Since parity games are in the intersection of NP and co-NP, even UP and co-UP, surely they admit a polynomial-time solution? The quest is therefore not finished, the question remains open: can we solve parity games in polynomial time? Or can we not, and would that imply that parity games separate P and NP? We focus our attention on algorithms that repeatedly partition parity games using attractors, extended with knowledge of tangles. Tangles are subgames that are won by one player, forcing the other player to escape the tangle. By repeatedly partitioning the game and obtaining new tangles from the partition, tangle learning algorithms solve parity games. Our journey so far has focused on designing various variations of tangle learning and subsequently exploring examples that maximally distract and delay these tangle learning variations.