论文标题
定时游戏的一个赌注是pspace-hard
One-Clock Priced Timed Games are PSPACE-hard
论文作者
论文摘要
本文的主要结果是，计算一个单盘定价的时机（OCPTG）的值是PSPACE-HARD。在此过程中，我们提供了一个具有指数级事件点的OCPTG家族。即使在具有Tree Wwidth Tirth的DAG等非常有限类的游戏中，这两个结果也会成立。最后，我们提供了许多积极的结果，包括更多限制性OCPTG（例如树）的多项式时间算法。
The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponential number of event points. Both results hold even in very restricted classes of games such as DAGs with treewidth three. Finally, we provide a number of positive results, including polynomial-time algorithms for even more restricted classes of OCPTGs such as trees.
