eng
episciences.org
Logical Methods in Computer Science
1860-5974
2022-05-26
Volume 18, Issue 2
10.46298/lmcs-18(2:12)2022
7303
journal article
CC-circuits and the expressive power of nilpotent algebras
Michael Kompatscher
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.
https://lmcs.episciences.org/7303/pdf
Mathematics - Rings and Algebras
Computer Science - Computational Complexity
08A70, 08A40