paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A parameterized halting problem, the linear time hierarchy, and the MRDP theorem

参数化停机问题、线性时间层级与 MRDP 定理
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 1/10 · 该论文属于纯计算复杂性与逻辑理论，研究参数化停机问题与线性时间层次的关系，与静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接关联；仅“停机问题”与程序分析有非常间接的理论联系。引用 4 inbox
Yijia Chen, Moritz Müller, Keita Yokoyama
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：将参数化停机问题 p-Halt 是否属于 para-AC0 与经典复杂性开放问题 NE ⊈ LINH 相联系，表明其难以判定。

本文研究非确定图灵机参数化停机问题 p-Halt 的复杂度。已知 p-Halt 是否属于 para-AC0 与 AC0（等价于 (+,×)-不变一阶逻辑 FO）能否被逻辑刻画密切相关，尽管社区普遍相信 p-Halt ∉ para-AC0，但该断言一直缺乏依据。作者通过建立 p-Halt 与经典复杂性中“NE 是否不包含于线性时间层级 LINH”这一开放问题的联系，证明该问题难以解决：若能判定 p-Halt 在 para-AC0 中的归属，就会对 NE 与 LINH 的比较产生重要影响。这一结果说明 p-Halt 的 para-AC0 成员性问题不太可能用现有方法轻易解决，也把参数化复杂度与经典描述复杂度问题联系起来。

问题
研究 p-Halt 是否属于 para-AC0，以及这一归属与 AC0 的逻辑刻画之间的关系。
方法
通过建立参数化停机问题与经典复杂性开放问题 NE ⊈ LINH 之间的联系，进行理论归约与复杂性论证。
评估
以理论证明为主，表明 p-Halt 的 para-AC0 成员性问题难以解决，并将其与 NE 和 LINH 的比较问题关联。
原文摘要（Abstract）

The complexity of the parameterized halting problem for nondeterministic Turing machines p-Halt is known to be related to the question of whether there are logics capturing various complexity classes [10]. Among others, if p-Halt is in para-AC0, the parameterized version of the circuit complexity class AC0, then AC0, or equivalently, (+, x)-invariant FO, has a logic. Although it is widely believed that p-Halt ∉. para-AC0, we show that the problem is hard to settle by establishing a connection to the question in classical complexity of whether NE ⊈ LINH. Here, LINH denotes the linear time hierarchy.

链接与引用

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

BibTeX 
@inproceedings{paperbot4312,
  title = {A parameterized halting problem, the linear time hierarchy, and the MRDP theorem},
  author = {Yijia Chen and Moritz Müller and Keita Yokoyama},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209155}
}