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.
翻译:我们用这一结果来形容和讨论Barrington、Strubing和Th\'erien的新的代数模型,该模型指出,受约束深度的CC电路需要指数大小来计算和计算。此外,我们还调查了在固定的零能力代数中决定身份和解方程的复杂性。根据推测属实的假设,我们为这两个问题都获得了准极价算法。另一方面,如果并且能够由接合深度和多面体大小的统一的CC电路进行计算的话,我们可以建立一个零能力代数模型,用以核对身份是 CoNP的完整,而解方程是NP的完整。