Complexity Classes Arising from Circuits over Finite Algebraic Structures
Piotr Kawałek, Jacek Krzaczkowski · 2026
Read Complexity Classes Arising from Circuits over Finite Algebraic Structures by Piotr Kawałek, Jacek Krzaczkowski (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21831.txt.
Introduction
Kawałek and Krzaczkowski build a single algebraic frame for circuit complexity beyond the Boolean domain. Old results focus on Boolean circuits, partly because computers are built that way. Richer circuit landscapes over larger domains get lost in that focus. Building on Barrington's branching programs and nonuniform deterministic automata, and on Idziak's wider version, they sort out which languages circuits over simple algebras recognise, and over algebras from congruence modular varieties.
Catalog record
| CREATOR | Piotr Kawałek, Jacek Krzaczkowski |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111735 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.21831
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Complexity Classes Arising from Circuits over Finite Algebraic Structures Thanks: Piotr Kawałek: This research was funded in whole or in part by National Science Centre, Poland #2021/41/N/ST6/03907. For the purpose of Open Access, the author has applied a CC-BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission. Funded by the European Union (ERC, POCOCOP, 101071674). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Thanks: Jacek Krzaczkowski: This research was funded in whole or in part by National Science Centre, Poland #2022/45/B/ST6/02229. For the purpose of Open Access, the author has applied a CC-BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission. Piotr Kawałek, Jacek Krzaczkowski Abstract . Most classical results in circuit complexity theory concern circuits over the Boolean domain. Besides their simplicity and the ease of comparing different languages, the actual architecture of computers is also an important motivating factor. On the other hand, by restricting attention to Boolean circuits, we lose sight of the much richer landscape of circuits over larger domains. Our goal is to bridge these two worlds: to use deep algebraic tools to obtain results in computational complexity theory, including circuit complexity, and to apply results from computational complexity to gain a better understanding of the structure of finite algebras. In this paper, we propose a unifying algebraic framework which we believe will help achieve this goal. Our work is inspired by branching programs and nonuniform deterministic automata introduced by Barrington, as well as by their generalization proposed by Idziak et al. We begin our investigation by studying the languages recognized by natural classes of algebraic structures. In particular, we characterize language classes recognized by circuits over simple algebras and over algebras from congruence modular varieties. 1. Introduction It is the fact that algebraic insights can lead to breakthroughs in computational complexity theory. Let us only mention a few examples: polynomials over finite fields and their usefulness in establishing \mathsf{IP}=\mathsf{PSPACE} [ 24 , 35 ] ; modelling program verification with a Gröbner basis problems [ 34 , 32 ] ; the group-theoretic proof of Barrington that languages from NC^{1} can be recognized by bounded-width branching programs [ 7 ] ; currently explored machine learning algorithms heavily based on linear algebraic concepts [ 23 , 39 ] . One could enumerate so many more brilliant applications of algebra. There seem to be only a thin boundary between the world of Turing Machines and the world of Algebra. Perhaps the most demonstrative example of that in the past decade was the P vs. NP-complete dichotomy theorem for finite Constraint Satisfaction Problems (CSPs) [ 11 , 40 ] , which model a large class of natural algorithmic problems. In the theory of CSP the key idea was to study not only the combinatorial nature of the constraints which define the problem but rather the interaction between the combinatorics and the symmetries of the constraints. These symmetries, called polymorphisms, are multiary functions which are closed under compositions and preserve the constraints. They form a structure called a termal clone. The field of Universal Algebra, which studies termal clones for about a century now, is what enabled this big CSP research project. The other direction also holds and the computational complexity notions can help to understand some of the algebraic concepts deeper. A prime example of that are Nonuniform Deterministic Finite Automata studied by Barrington, Straubing and Thérien [ 4 ] , where the expressive power of polynomial-size expressions over finite groups are linked to circuit complexity classes. Here DFA appear because, due to associativity, one may interpret these nonuniform expressions as acting on the state set of the finite automaton. For instance, one can solve arbitrary problems in nonuniform NC^{1} (including all the problems with very effective parallel algorithms) with polynomial-size expressions over any nonsolvable group. On the contrary, solvable groups seem to have much smaller computational power as expressions over such groups can only solve problems that are also solvable by bounded-depth circuits (in the class CC^{0} ). Nilpotent groups provably have very small expressive power, as they essentially can only evaluate bounded-degree polynomials. Similar research was done for monoids, where expressions over solvable monoid seem to have more power than the ones of solvable groups [ 5 ] (they solve problems in the class ACC^{0} ). Later it was spotted that the insights from [ 4 ] can be used to obtain polynomial or quasipolynomial time algorithms for the problem of solving equations in solvable groups/monoids [ 8 , 16 ] . The problems of solving equations was then considered in a much more general context of finite algebras [ 18 ] , which means finite universes with arbitrary finite sets of operations. Note that the class of these problems is very reach as it generalizes class of all finite CSPs (see [ 18 ] ). The research was especially successful for the algebras from so-called congruence modular varieties. This algebras generalize most of the structures studied in classical algebra, such as groups, rings, Boolean Algebra, Heyting Algebras, Lie Algebras, lattices, latin matrices and many more. Recently some assumptions about circuit lower bounds have proven their usefulness in some variants of satisfiability problems for groups [ 19 ] as well as general algebras [ 20 ] to provide randomized polynomial time algorithms. In this paper we want to continue to study the connection between expressive power of circuits over finite algebras and classical Boolean circuit complexity classes. To define this correspondence correctly, we define how this multivalued circuits will be used to recognize languages. Say we have some finite universe A and some set of operations f_{1},\ldots,f_{k} over A that we will use as gates while building our circuit. This is our algebraic structure {\bf{A}} . Variables as well as constants from A can appear on the input level of such circuits. This connects our consideration to so called polynomial clone of {\bf{A}} , that is composition closed set of operations that contains constants from the universe. Let us say we have a language L\subseteq\Sigma^{*} we want to recognize. Then we need a way to project the alphabet \Sigma to the universe of our algebra, we need a way to interpret the result (we need the accepting set S\subseteq A ) and because there are many possible input lengths we need not only one circuit, but a sequence of circuits over {\bf{A}} (that is why this model of computation is called nonuniform). Definition 1 . Non-uniform Deterministic Finite Automaton (NuDFA) over a finite algebra {\bf{A}} consists of: • a sequence {\left\{{{\mathbf{t}}}\right\}}_{i=1}^{\infty} of circuits over {\bf{A}} such that circuit {\mathbf{t}}_{n} is n -ary. • function \iota:\Sigma\mapsto A , • set S\subseteq A , A word b_{1}\ldots b_{n}\in\Sigma^{n} gets accepted by such a NuDFA if {\mathbf{t}}_{n}(\iota(b_{1}),\ldots,\iota(b_{n}))\in S . A triple ({\mathbf{t}},\iota,S) where {\mathbf{t}} is an n -ary circuit is called an n -ary program (in correspondence to straight-line programs). We will write {\mathbf{t}}[\iota](\overline{b}) to denote {\mathbf{t}}(\iota(b_{1}),\ldots,\iota(b_{n})) and {\mathbf{t}}[\iota,S](\overline{b}) as a characteristic function of