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