paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Choiceless Polynomial Time with Witnessed Symmetric Choice

带见证对称选择的无选择多项式时间
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 0/10 · 该论文属于有限模型论与计算复杂性领域,研究 CPT 逻辑、对称选择与 Ptime 捕获能力,与用户关注的机器学习/Agentic 程序静态分析、LLM 辅助形式化验证、浮点程序分析及贝叶斯程序分析均无直接关联。引用 4 inbox
Moritz Lichter, Pascal Schweitzer
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:通过引入带见证对称选择扩展 CPT,使可定义同构自动蕴含可定义规范化,并在同构可定义结构类上自动捕捉 Ptime。

Choiceless Polynomial Time(CPT)是当前有望刻画 Ptime 的逻辑候选。本文针对在特定结构类上证明 CPT 捕捉 Ptime 时,从同构可定义性推广到规范化需要大量额外工作的难题,扩展 CPT 引入带见证的对称选择算子。该算子允许从可定义轨道中选择元素,但要求提供自同构作为见证以证明选择集确为轨道,从而保证多项式时间求值。作者证明,在该扩展逻辑中,可定义同构蕴含可定义规范化。因此,对任何同构可定义的结构类,该逻辑自动捕捉 Ptime,消除了原有证明中非平凡的推广步骤。

问题
CPT 是刻画 Ptime 的候选逻辑,但在特定结构类上证明其捕捉 Ptime 时,从同构可定义性推出规范化需要非平凡的额外步骤。
方法
扩展 CPT,加入带见证的对称选择算子:允许从可定义轨道选择,并要求以自同构作为见证来保证选择集确为轨道,同时维持多项式时间求值;进而证明可定义同构蕴含可定义规范化。
评估
在有限模型论与描述复杂性框架下给出理论证明:该扩展逻辑对同构可定义的结构类自动捕捉 Ptime,从而消除从同构定义性到规范化的额外证明负担;论文未涉及实现或实验评估。
原文摘要(Abstract)

We extend Choiceless Polynomial Time (CPT), the currently only remaining promising candidate in the quest for a logic capturing Ptime, so that this extended logic has the following property: for every class of structures for which isomorphism is definable, the logic automatically captures Ptime. For the construction of this logic we extend CPT by a witnessed symmetric choice operator. This operator allows for choices from definable orbits. But, to ensure polynomial time evaluation, automorphisms have to be provided to certify that the choice set is indeed an orbit. We argue that, in this logic, definable isomorphism implies definable canonization. Thereby, we remove the non-trivial step of extending isomorphism definability results to canonization. This step was a part of proofs that show that CPT or other logics capture Ptime on a particular class of structures. The step typically required substantial extra effort.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{LichterS22,
  title = {Choiceless Polynomial Time with Witnessed Symmetric Choice},
  author = {Moritz Lichter and Pascal Schweitzer},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533348}
}