paperbot · PL 论文追踪

全部论文 待读 收藏

P2 CC-circuits and the expressive power of nilpotent algebras

CC-电路与幂零代数的表达能力
LMCS vol.Volume 18, Issue 22022匹配度 0/10 · 该论文研究有界深度 CC-电路与幂零代数的表达力等价,属于代数电路复杂度与逻辑/自动机理论,与用户关注的程序静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析均无直接关联。引用 4 inbox
Michael Kompatscher
crossref: 2026-09-10

AI 速览

一句话:证明有界深度 CC-电路与同余模簇中有限幂零代数上的电路表达力等价,并联系代数版 B-S-T 猜想。

论文研究有界深度 CC-电路的表达能力,并将其与有限幂零代数上的电路联系起来。作者证明:有界深度 CC-电路与来自同余模簇的有限幂零代数上的电路具有相同的表达能力。由此,论文提出并讨论 Barrington、Straubing 和 Thérien 猜想的一个代数版本,即用有界深度 CC-电路计算 AND 需要指数规模。论文还考察固定幂零代数中判定恒等式与求解方程的复杂度:若该猜想成立,两个问题都有拟多项式算法;若 AND 可由多项式规模的一致有界深度 CC-电路计算,则可构造幂零代数使恒等式检查为 coNP-完全、方程求解为 NP-完全。

问题
刻画有界深度 CC-电路的表达能力,并探讨其与有限幂零代数电路及 Barrington–Straubing–Thérien 猜想代数版本的联系。
方法
利用同余模簇中的有限幂零代数给出电路表达能力的代数刻画,并分析固定幂零代数中恒等式判定与方程求解的复杂度。
评估
在 B-S-T 代数猜想成立与否两种情形下分别给出复杂度结论:成立时得到拟多项式算法,否证式假设下得到 coNP-完全与 NP-完全结果。
原文摘要(Abstract)

We show that CC-circuits of bounded depth have the same expressive power as circuits over finite nilpotent algebras from congruence modular varieties. We use this result to phrase and discuss a new algebraic version of Barrington, Straubing and Th\'erien's conjecture, which states that CC-circuits of bounded depth need exponential size to compute AND. Furthermore, we investigate the complexity of deciding identities and solving equations in a fixed nilpotent algebra. Under the assumption that the conjecture is true, we obtain quasipolynomial algorithms for both problems. On the other hand, if AND is computable by uniform CC-circuits of bounded depth and polynomial size, we can construct a nilpotent algebra in which checking identities is coNP-complete, and solving equations is NP-complete.

链接与引用

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

BibTeX
@article{paperbot1699,
  title = {CC-circuits and the expressive power of nilpotent algebras},
  author = {Michael Kompatscher},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 2},
  year = {2022},
  doi = {10.46298/lmcs-18(2:12)2022}
}