一句话:引入完美半空间博弈并证明其位置确定性,进而以伪多项式时间求解多维能量奇偶博弈。
论文研究多维能量奇偶博弈的求解与复杂度问题,特别是在能量维数和优先级数固定时,无论初始信用作为输入的一部分还是存在量化。作者引入完美半空间博弈,其中玩家2动态选择一列完美半空间,目标是使遇到的多维权重和沿一致方向发散。论文证明 Jurdziński 等人的 bounding games 可归约到完美半空间博弈,后者又可翻译为 Colcombet 与 Niwiński 的字典序能量博弈,并具有强位置确定性:玩家2无需知道当前完美半空间即可行动。作为应用,这些博弈被用于在固定能量维数和优先级数时以伪多项式时间求解多维能量奇偶博弈;在给定初始信用时得到最优 2-EXPTIME 复杂度,而此前最好上界为非初等。
We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional weights diverge in a direction which is consistent with a chosen sequence of perfect half spaces (chosen dynamically by Player 2). We establish that the bounding games of Jurdziński et al. (ICALP 2015) can be reduced to perfect half space games, which in turn can be translated to the lexicographic energy games of Colcombet and Niwiński, and are positionally determined in a strong sense (Player 2 can play without knowing the current perfect half space). We finally show how perfect half space games and bounding games can be employed to solve multi-dimensional energy parity games in pseudo-polynomial time when both the numbers of energy dimensions and of priorities are fixed, regardless of whether the initial credit is given as part of the input or existentially quantified. This also yields an optimal 2-EXPTIME complexity with given initial credit, where the best known upper bound was non-elementary.