Recursive Solving Of Parity Games Requires Exponential Time
Recursive Solving Of Parity Games Requires Exponential Time
复制标题
递归求解奇偶游戏需要指数时间
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Oliver Friedmann
中科院分区：
文献类型：
--
作者：
Oliver Friedmann
本文提出了解决奇偶博弈的递归算法的新下界，该算法是由 Zielonka 的无记忆确定性的构造性证明导出的。我们概述了一系列线性大小的游戏，其算法需要指数时间。
This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.