paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Towards Uniform Certification in QBF

迈向 QBF 中的统一认证
LMCS vol.Volume 20, Issue 12024匹配度 2/10 · 该论文属于 QBF 证明复杂度与证明系统模拟,虽与形式化验证/定理证明相关,但未涉及用户关注的静态分析、LLM/Agent 与程序分析交叉、浮点程序分析或贝叶斯程序分析。其研究目标也不是用 LLM/Agent 改进形式化验证,因此与当前研究画像核心方向匹配度很低。引用 2 inbox
Leroy Chew, Friedrich Slivovsky
crossref: 2026-09-10

AI 速览

一句话:提出策略提取模拟技术,证明扩展 QBF Frege 可 p-模拟多种子句 QBF 证明系统,支持 QBF 求解统一认证。

本文研究 QBF 证明复杂度中的模拟问题,并面向 QBF 求解的认证需求。作者提出一种新技术:将 Beyersdorff 等人把策略提取转化为模拟的方法,与新的局部策略提取论证相结合。利用该技术,他们证明扩展 QBF Frege 可 p-模拟多种子句证明系统,包括 IR-Calculus、IRM-Calculus、Long-Distance Q-Resolution 和 Merge Resolution。这些模拟主要在命题逻辑中完成,仅最小程度地使用 QBF 规则,从而为被模拟系统提供了新的、大体命题化的解释。作者认为,大量 QBF 证明系统由此归入扩展 QBF Frege 之下,强化了 QBF 求解中统一认证的论据。

问题
QBF 证明复杂度中仍有若干模拟关系尚待建立,同时 QBF 求解需要统一的认证基础。
方法
将策略提取转化为模拟的既有技术扩展为局部策略提取论证,并尽量在命题逻辑层面构造模拟,仅少量使用 QBF 规则。
评估
通过证明扩展 QBF Frege 对 IR-Calculus、IRM-Calculus、Long-Distance Q-Resolution 与 Merge Resolution 的 p-模拟,展示该技术可统一多个 QBF 证明系统。
原文摘要(Abstract)

We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q-Resolution, and Merge Resolution. These results are obtained by taking a technique of Beyersdorff et al. (JACM 2020) that turns strategy extraction into simulation and combining it with new local strategy extraction arguments. This approach leads to simulations that are carried out mainly in propositional logic, with minimal use of the QBF rules. Our proofs therefore provide a new, largely propositional interpretation of the simulated systems. We argue that these results strengthen the case for uniform certification in QBF solving, since many QBF proof systems now fall into place underneath extended QBF Frege.

链接与引用

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

BibTeX
@article{paperbot2777,
  title = {Towards Uniform Certification in QBF},
  author = {Leroy Chew and Friedrich Slivovsky},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 20, Issue 1},
  year = {2024},
  doi = {10.46298/lmcs-20(1:14)2024}
}