一句话：将 ω-正则延迟博弈的求解复杂度与所需前瞻量从双指数改进为指数，并给出紧界。
延迟博弈是无限时长的双人博弈，其中一方可以推迟落子，从而获得对对手动作的前瞻。对 ω-正则获胜条件，已有工作给出双指数时间算法，并证明双指数前瞻充分。本文改进这两个结果：给出指数时间算法，并证明指数前瞻上界；同时证明求解问题是 EXPTIME 难的，且前瞻存在紧指数下界。这些下界对安全性条件已经成立。此外，可及性条件的延迟博弈求解被证明是 PSPACE 完全的。
Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent's moves. For $\omega$-regular winning conditions it is known that such games can be solved in doubly-exponential time and that doubly-exponential lookahead is sufficient. We improve upon both results by giving an exponential time algorithm and an exponential upper bound on the necessary lookahead. This is complemented by showing EXPTIME-hardness of the solution problem and tight exponential lower bounds on the lookahead. Both lower bounds already hold for safety conditions. Furthermore, solving delay games with reachability conditions is shown to be PSPACE-complete. This is a corrected version of the paper https://arxiv.org/abs/1412.3701v4 published originally on August 26, 2016.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{KleinZ14,
title = {How Much Lookahead is Needed to Win Infinite Games?},
author = {Felix Klein and Martin Zimmermann},
journal = {Logical Methods in Computer Science},
volume = {Volume 12, Issue 3},
year = {2017},
doi = {10.2168/lmcs-12(3:4)2016}
}