Beschreibung:
<jats:p>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.</jats:p>