拟多项式时间的平均支付奇偶博弈
Mean-payoff parity games in quasipolynomial time
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件给出平均支付奇偶博弈的统一确定性拟多项式时间算法。算法计算玩家能同时强制非负liminf平均支付与奇偶条件的全部顶点，允许任意带符号二进制奖励与无限制二进制优先级。运行时间为2^{O((log(L+2))²)}次位运算，其中L为完整输入长度。该结果改进此类博弈的算法复杂度上界。
- 给出平均支付奇偶博弈的统一确定性拟多项式时间算法
- 计算能同时强制非负liminf平均支付与奇偶条件的全部顶点
- 运行时间为2^{O((log(L+2))²)}次位运算，L为完整输入长度
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We give a uniform deterministic quasipolynomial-time algorithm for mean-payoff parity games. It computes all vertices from which a player can enforce both nonnegative liminf mean payoff and the parity condition, with arbitrary signed binary rewards and unrestricted binary priorities. The running time is $`2^{O((\log(L+2))^2)}`$ bit operations, where L is the complete input length.
用户标记：未标记
固定编号：40362631b0aa9eec
原文来源