Implicit computational complexity is an active 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 1965 when Cobham introduced a function algebra closed under bounded recursion on notation (BRN) to capture FP. Later on, several complexity classes have been characterized using limited recursion schemas. In this context, an original approach was recently introduced, showing that ordinary diferential equations (ODEs) ofer a natural tool for algorithmic design and providing a characterization of FP by a new ODE-schema. The overall goal of our project is precisely that of generalizing this approach to parallel computation: starting with original ODE-characterizations for the small circuit classes FAC0 and FTC0, we aim to uniformly capture the whole hierarchies FAC and FNC.
As computability theory investigates the limits of what is algorithmically computable, complexity theory classifies functions based on the amount of resources required by a machine to compute them. Taking a diferent viewpoint, implicit computational complexity aims to provide machineindependent characterizations, to ofer remarkable insights on the corresponding classes and related meta-theorems in several domains, from database theory to constraint satisfaction.
One of the major approaches to computability and (implicit) complexity is constituted by
the study of recursion. Groundbreaking results in this area were due to Cobham [
Although small circuit classes have been characterized in multiple ways, the questions of whether they can be studied through ODE lenses and whether this would shed some new light on their features are still open. To us, these questions are interesting as, for a descriptive approach based on ODEs to make sense and be fruitful, it has to be able to cope with very subtle and restricted modes of computation. They are also challenging as even simple and useful mathematical functions may not be computable in the classes we are considering (e.g. multiplication is not in FAC0); consequently, tools at hand and the naturalness of the approach are drastically restricted. Our project aims to investigate these questions and to find natural ODE-oriented function algebras to capture small circuit classes. So far, we have focused on the characterization of functions computable by families of polynomial size and constant depth circuits (FAC0), possibly including majority gates (FTC0). In particular, in [31], we have captured both these classes by means of special ODE-schemas, obtained by deriving along the logarithmic function and intuitively allowing for bit shifting operations through restricted forms of linear equations. These case studies are intended as the first step towards a uniform characterization of other relevant classes in the FAC and FNC hierarchies.
As anticipated, a foundational result in recursion theory was established by Cobham [
(, y) ≤ (, y) for all , y.
In BRN, the growth of the defined function is controlled by another function (in FP), while
the number of induction steps is kept under control by the application of the binary successor
functions s() = 2 + , ∈ {0, 1}. However, such a schema is in a sense not fully satisfactory
as it imposes an explicit bound on recursion in the form of an already known function.
1Other implicit characterizations based on schemas and restrictions on first-order programs have been recently
introduced [
Cobham’s seminal work not only led to a variety of implicit characterizations for classes other than FP, but also inspired alternative approaches to capture this class. Among them, the proposal by [28] has the peculiarity of neither imposing any explicit bound on the recursion schema nor assigning specific roles to variables. Indeed, it is based on special discrete ODEs, which combine two peculiar features: deriving along specific functions , so to control the number of computation steps, and linearity, namely a special syntactic form of the equation allowing to control the object size.
Recall that the discrete derivative of f (x) is defined as ∆ f () = f ( + 1) + f () and that ODEs are expressions of the form: f (, y) = h(︀ f (, y), , y)︀ ,
where f(,y) stands for the derivative of f (, y) considered as a function of , for y fixed.
When some initial value f (0, y) = g(y) is added, this is called Initial Value Problem (IVP). In addition, let sg : Z → Z be the sign function over Z, taking value 1 for > 0 and 0 otherwise. A sg-polynomial expression (1, . . . , ℎ) is an expression built over the signature {+, − , ×} , the function sg and a set of variables = {1, . . . , ℎ}, plus integer constants. A sg-polynomial expression is said to be essentially linear in a set of variables , if there exist sg-polynomial expressions 1 and 2 such that = 1 × + 2 and, in 1 and 2, occurs only under the scope of sg.
Definition 1 (Linear -ODE). Given g : N → Z, h, : N+1 → Z and u : Z × N+2 → Z, the function f : N+1 → Z is linear -ODE definable from g, h and u if it is the solution of the IVP with initial value f (0, y) = g(y) and such that: f (, y) = u(︀ f (, y), h(, y), , y)︀ (1) with u essentially linear in the list of terms f (, y).
For ̸= 0, let ℓ() denote the length of written in binary, i.e. ⌈log2( + 1)⌉, and ℓ(0) = 0. For = ℓ, the schema above is called linear length ODE, ℓ-ODE. () = ∏︀ℓ(=0)− 1 2 = 2ℓ().
Example 1 (Function 2ℓ()). The function ↦→ 2ℓ() can be seen as the solution of the IVP with initial value (0) = 1 and such that () = (). The solution of this system is of the form ℓ
One of the main results of [28] is the implicit characterization of FP by the algebra made of basic functions 0, 1, , ℓ, +, − , × , sg and closed under composition (∘ ) and ℓ-ODE:
LDL = [0, 1, , ℓ, +, − , sg; ∘ , ℓ-ODE].
So far, our investigation of parallel complexity via ODEs has focussed on the smallest classes in the hierarchies FAC and FTC.
Definition 2 (Classes FAC and FTC). For ∈ N, AC (resp., TC) is the class of languages recognized by a Dlogtime-uniform family of Boolean circuits (resp., circuits including majority gates) of polynomial size and depth ((log )). We denote by FAC and FTC the corresponding function classes.
In particular, in [31], we have provided the first implicit characterizations of FAC0 and FTC0 in the ODE setting. To do so, our key ingredient is the introduction of new function algebras, the defining feature of which is the presence of special ODE schemas, intuitively corresponding to left- and right-shifting.2 The schema below intuitively corresponds to left-shifting and (possibly) adding a bit. function : N+1 initial value (0, y) = (y) and such that: Definition 3 ( ℓ-ODE2 Schema). Given : N → N, ℎ : N+1 → N and : N → N, the → N is defined by ℓ-ODE2 from , ℎ and if it is the solution of the IVP with (2) (3) where ℎ(, y) ∈ {0, 1} and, if, for some , y, ℎ(, y) ̸= 0, then (y) ̸= 0.
Observe that, since this schema is introduced to characterize FAC0, the constraint imposing (y) ̸= 0, when there exist , y such that ℎ(, y) = 1, is really essential. If we omit it, ℓ-ODE2 will be too strong, as able to capture binary counting (which is not in FAC0). However, this schema is not as weak as it may seem since, together with sg, it sufices to express bounded quantification.
The second new schema we need corresponds to the (basic) right-shifting operation. Definition 4 ( ℓ-ODE3 Schema). Given : N → N, the function : N+1 → N is defined by ℓ-ODE3 from if it is the solution of the IVP with initial value (0, y) = (y) and such that: where ⌈ 2 ⌉ is a shorthand for − ( ÷ 2), and ÷ 2 denotes integer division by 2. Remarkably, the following closure property holds for both schemas.
Proposition 1. If is defined by ℓ-ODE2 or ℓ-ODE3 from functions in FAC0, then is in FAC0 as well.
It is relying on these schemas that we define the following ODE-style class:
ACDL = [0, 1, , ℓ, +, − , ÷ 2, sg; ∘ , ℓ-ODE2, ℓ-ODE3]. 2Observe that our schemas are defined using × . This is acceptable since, the “kind of multiplication” we consider to define them is limited to special cases (namely, multiplications by 2), which are provably computable in FAC0. Notice that all its basic functions and (restricted) schemas are natural in the context of diferential equations and calculus. Of course, in ACDL, multiplication is not allowed. In addition, the -ODE schema is here substituted by the two schemas ℓ-ODE2 and ℓ-ODE3, characterized by a very limited form of “multiplication” and, as said, intuitively capturing left and right shifting.
This class is shown able to characterize FAC0.
Theorem 1. FAC0 = ACDL.
In particular, our proof that FAC0 ⊆ and schema defining Clote’s function algebra for
ACDL is indirect, namely we show that any basic function
FAC0 [
As a byproduct, an ODE-characterization for FTC0 is also established (this time passing through Clote and Takeuti’s function algebra [22]) by simply considering an extension of ACDL, obtained by endowing it with the basic function × :
TCDL = [0, 1, , ℓ, +, − , ÷ 2, × , sg; ∘ , ℓ-ODE2, ℓ-ODE3] In addition, an alternative characterization of FTC0 can be introduced by substituting the ℓ-ODE2 schema in the definition of ACDL with its more liberal version ℓ-ODE*2. takes values in {0, 1}. Then, the function : N+1 → N is defined by when it is the solution of the IVP with initial value (0, y) = (y) and such that: Definition 5 ( ℓ-ODE*2 Schema). Let : N → N, ℎ : N+1 → N and : N
→ N, where ℎ ℓ-ODE*2 from , ℎ and expressed via ℓ-ODE*2. Let bit(, ) be a special bit function returning 1 when the ℓ()ℎ bit of is 1 (which can be rewritten already in ACDL). Then, bcount() = (, ), where is the solution of the IVP with initial value (0, y) = bit(0, y) and such that (,y) = bit(, y). It is easy to see that the ℓ-ODE*2 schema is enough not only to express binary counting but, more in ℓ general, to capture majority computation.
Proposition 2. FTC0 = TCDL = [0, 1, , ℓ, +, − , ÷ 2, sg; ∘ , ℓ-ODE*2, ℓ-ODE3]
We conceive our characterizations of FAC0 and FTC0 as the first step in a project aiming
to capture several other relevant classes, starting with FAC and FNC. Indeed, the
restrictions of linear ODE schemas we have adopted are surprisingly natural, and we believe that a
similar analysis would also make it possible to capture computation corresponding to -BRN
and -BRN [
The first two authors thank Maupertuis Program, on behalf of the Institut Français de Finlande, the Embassy of France in Finland, the French Ministry of Higher Education and Research and the Finnish Society of Sciences and Letters, for financially supporting their research. They also thank the ANR Project Diference. The first author is grateful to HIIT for supporting her work since 2023. [19] D. Barrington, N. Immerman, H. Staubing, On uniformity within NC1, J. of Comput. and
Syst. Sc. 41 (1990) 274–306. [20] Y. Gurevich, H. Lewis, A logic for constant-depth circuit, Inf. Control 61 (1984) 65–74. [21] S. Lindell, A purely logical characterization of circuit uniformity, in: 7th Structure in
Complexity Theory Conf., 1992, pp. 185–192. [22] P. Clote, G. Takeuti, First order bounded arithmetic and small complexity classes, in:
Feasible Mathematics II, Clote, P.G. and Remmell, J.B., 1995, pp. 154–218. [23] J. Johannsen, A bounded arithmetic theory for constant depth threshold circuit, in: P. Hájek (Ed.), GÖDEL ’96: Logical foundations of mathematics, computer science and physics, 1996, pp. 224–234. [24] S. Cook, P. Nguyen, Theories for TC0 and other small circuit classes, Log. Meth. Comput.
Sci. 2 (2006). [25] T. Arai, A bounded arithmetic AID for Frege systems, Ann. Pure Appl. Logic 103 (2000) 155–199. [26] S. Cook, T. Morioka, Quantified propositional calculus and second-order theory for NC 1,
Arch. Math. Logic 44 (2005) 711–749. [27] D. Leivant, Y.-Y. Marion, Lambda calculus characterizations of poly-time, Fundam. Inform.
19 (1993) 167–184. [28] O. Bournez, A. Durand, A characterization of functions over the integers computable in polynomial time using discrete diferential equations, Comput. Complex. 32 (2023). [29] M. Blanc, O. Bournez, A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary diferential equations, in: Proc. MCU, 2022, pp. 58–74. [30] M. Blanc, O. Bournez, A characterization of functions computable in polynomial time and space over the reals with discrete ordinary diferential quations, in: Proc. MFCS, 2023, pp. 21:1–21:15. [31] M. Antonelli, A. Durand, J. Kontinen, A new characterization of FAC0 via discrete ordinary diferential equations, in: Proc. MFCS, 2024. [32] P. Clote, A sequential characterization of the parallel complexity class NC, Technical Report, Boston College, 1988.