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