Descriptive Complexity of $\#{\text{AC}}^0$ Functions

Arnaud Durand, Anselm Haak, Juha Kontinen +1

We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free fu…