Towards new characterizations of small circuit classes via discrete ordinary differential equations
Melissa Antonelli, Arnaud Durand, Juha Kontinen · Theoretical Computer Science · 2025
Implicit computational complexity is a lively area of theoretical computer science, which aims to provide machine-independent characterizations of relevant complexity classes. One of the seminal works in this field appeared in the 1960s, when Cobham introduced a function algebra closed under bounded recursion on notation to capture polynomial time computable functions ( FP ). Later on, several complexity classes have been characterized using limited recursion schemas. In this context, an original approach has been recently introduced, showing that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and providing a characterization of FP by a new ODE-schema. In the present paper we generalize this approach by presenting original ODE-characterizations for the small circuit classes FAC 0 and FTC 0 .