paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Uniform, integral and efficient proofs for the determinant identities

行列式恒等式的统一、整数与高效证明
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 该论文属于证明复杂度、有界算术与代数电路算法,虽与形式化证明理论相关,但未涉及用户核心方向中的 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析。它也没有工业工具落地、benchmark 失效分析或 LLM 与形式化验证交叉的内容。引用 4 inbox
Iddo Tzameret, Stephen A. Cook
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:在 VNC2 中证明整数上行列式乘法性,给出统一的 O(log²n)-深度多项式规模 Circuit-Frege 证明及 NC2 代数电路算法。

本文研究行列式恒等式在整数上的短命题证明能否统一且高效。此前 Hrubeš 与 Tzameret 仅在 GF(2) 上给出了短证明。作者在对应 NC2 的有界算术理论 VNC2 中形式化了行列式函数的乘法性,并据此构造出整数上基本行列式恒等式的统一多项式规模、O(log² n) 深度 Circuit-Frege(等价 Extended Frege)证明。为完成证明,还给出 VNC2 中 Σ1B-可定义的统一 NC2 算法:齐次化代数电路、平衡代数电路(给定语法次数上界),以及把带除法门电路转换为仅含单个除法门的电路。这些算法也蕴含任意深度代数电路的 NC2 求值算法。

问题
此前行列式恒等式的短命题证明仅在 GF(2) 上可得,整数上的统一、高效证明及其与有界算术的关系尚不明确。
方法
在有界算术理论 VNC2 中形式化证明,并设计 Σ1B-可定义的 NC2 算法用于齐次化、平衡代数电路和消除除法门。
评估
通过 VNC2 可证性推出 Circuit-Frege/Extended Frege 证明的规模与深度上界,并导出代数电路求值的 NC2 算法。
原文摘要(Abstract)

We give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over GF(2) in Hrubeš-Tzameret [9]. Specifically, we show that the multiplicativity of the determinant function over the integers is provable in the bounded arithmetic theory VNC2, which is a first-order theory corresponding to the complexity class NC2. This also establishes the existence of uniform polynomial-size and O(log2n)-depth Circuit-Frege (equivalently, Extended Frege) proofs over the integers, of the basic determinant identities (previous proofs hold only over GF(2)). In doing so, we give uniform NC2-algorithms for homogenizing algebraic circuits, balancing algebraic circuits (given as input an upper bound on the syntactic-degree of the circuit), and converting circuits with divisions into circuits with a single division gate-all (Σ1B-) definable in VNC2. This also implies an NC2-algorithm for evaluating algebraic circuits of any depth.

链接与引用

DOI 原文 · DBLP

BibTeX
@inproceedings{TzameretC17,
  title = {Uniform, integral and efficient proofs for the determinant identities},
  author = {Iddo Tzameret and Stephen A. Cook},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005099}
}