Michael Kompatscher - CC-circuits and the expressive power of nilpotent algebras

lmcs:7303 - Logical Methods in Computer Science, May 26, 2022, Volume 18, Issue 2 - https://doi.org/10.46298/lmcs-18(2:12)2022
CC-circuits and the expressive power of nilpotent algebras

Authors: 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érien'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.

    Volume: Volume 18, Issue 2
    Published on: May 26, 2022
    Accepted on: March 29, 2022
    Submitted on: March 29, 2021
    Keywords: Mathematics - Rings and Algebras,Computer Science - Computational Complexity,08A70, 08A40


    Consultation statistics

    This page has been seen 486 times.
    This article's PDF has been downloaded 409 times.