paperbot · PL 论文追踪

全部论文 待读 收藏

P2 One-Clock Priced Timed Games are PSPACE-hard

单时钟定价时间博弈是 PSPACE-难的
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 2/10 · 该论文属于定价时间博弈与自动机理论，研究单时钟博弈的复杂度，与用户核心方向（LLM/Agent 与静态分析、浮点程序分析、贝叶斯程序分析的交叉）无直接关联。它既不涉及程序分析或 LLM，也没有工程实现与工业落地内容。引用 0 inbox
John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：证明单时钟定价时间博弈的值计算是 PSPACE-难的，即使限制在树宽为三的 DAG 上，并给出树等受限类的多项式算法。

本文研究单时钟定价时间博弈（OCPTG）的值计算复杂度。作者证明该问题是 PSPACE-难的，并构造了一类具有指数多个事件点的 OCPTG，从而揭示其复杂来源。该难性甚至在最受限的博弈类（如树宽为三的 DAG）中依然成立。作为正面结果，论文给出了若干更受限 OCPTG 类的多项式时间算法，包括树结构。这些结果刻画了 OCPTG 值计算问题在一般情形与受限结构下的可解性边界。

问题
计算单时钟定价时间博弈（OCPTG）的值，并确定其计算复杂度，尤其是 PSPACE-难性边界。
方法
通过构造具有指数多事件点的 OCPTG 族并分析受限博弈类（如树宽为三的 DAG），证明一般问题的 PSPACE-难性；对树等更受限类设计多项式时间算法。
评估
以理论复杂性证明和算法结果进行评估，覆盖一般 OCPTG 的 PSPACE-难性及若干受限类的多项式可解性。
原文摘要（Abstract）

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.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot5499,
  title = {One-Clock Priced Timed Games are PSPACE-hard},
  author = {John Fearnley and Rasmus Ibsen-Jensen and Rahul Savani},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394772}
}