一句话：提出基于 register-index 的奇偶博弈新准多项式求解算法，固定参数下多项式可解。
奇偶博弈（parity games）的求解复杂度是模态 μ 演算与自动机理论中的核心问题，寻找准多项式时间算法长期受到关注。论文从模态 μ 演算的视角出发，引入一种新的双模拟不变复杂度度量 register-index，用它刻画博弈中优先级赋值的复杂度。基于该度量，论文给出新的准多项式时间求解算法，并证明当 register-index 以固定参数 k 为界时，相应博弈类可在多项式时间内求解。
We present a new quasi-polynomial algorithm for solving parity games. It is based on a new bisimulation invariant measure of complexity for parity games, called the register-index, which captures the complexity of the priority assignment. For fixed parameter k, the class of games with register-index bounded by k is solvable in polynomial time.
DOI 原文 ·
@inproceedings{paperbot4349,
title = {A modal μ perspective on solving parity games in quasi-polynomial time},
author = {Karoliina Lehtinen},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209115}
}