Characterizing Small Circuit Classes from ${\mathrm{𝐅𝐀𝐂}}^{\mathrm{𝟎}}$ to ${\mathrm{𝐅𝐀𝐂}}^{\mathrm{𝟏}}$ via Discrete Ordinary Differential Equations

One of the main approaches developed in implicit computational complexity is that based on recursion. It was initiated by Cobham [18], who gave the first characterization for $\mathrm{𝐅𝐏}$ via a limited recursion schema. This groundbreaking result has inspired not only similar characterizations for other classes, but also alternative recursion-based approaches to capture poly-time computable functions, such as safe recursion [6] and ramification [28, 29]. Among them, the proposal by [10] offers the advantages of not imposing any explicit bound on the recursion schema or assigning specific role to variables. Instead, it is based on Discrete Ordinary Differential Equations (a.k.a. Difference Equations) and combines two novel features, namely derivation along specific functions, to control the number of computation steps, and a special syntactic form of the equation (linearity), to control the object size.

Recall that the discrete derivative of $𝐟(x)$ is defined as $\mathrm{\Delta }𝐟(x)=𝐟(x+1)-𝐟(x)$, and that ODEs are expressions of the form

where $\frac{\partial 𝐟(x,𝐲)}{\partial x}$ stands for the derivative of $𝐟(x,𝐲)$ considered as a function of $x$, for a fixed value for $𝐲$. When some initial value $𝐟(0,𝐲)=𝐠(𝐲)$ is added, this is called Initial Value Problem (IVP). Then, in order to deal with complexity, some restrictions are needed. First, we introduce the notion of derivation along functions.

Notice that the value of $\mathrm{\ell }(x)$ changes (it increases by 1) when $x$ goes from $2^t-1$ to $2^t$ (for $t\ge 1$). Similarly, the value of ${\mathrm{\ell }}_2(x)$ changes when $x$ goes from $2^{2^1-1}-1$ to $2^{2^t-1}$ (for $t\ge 1$).

Intuitively, one of the key properties of the $\lambda$-ODE schema is its dependence on the number of distinct values of $\lambda$, i.e., the value of $𝐟(x,𝐲)$ changes only when the value of $\lambda (x,𝐲)$ does. Computation of solutions of $\lambda$-ODEs have been fully described in [11]. Here, we focus on the special case of $\lambda =\mathrm{\ell }$, which is particularly relevant for our characterizations. If $𝐟$ is a solution of (1) with $\lambda =\mathrm{\ell }$ and initial value $𝐟(0,𝐲)=𝐠(𝐲)$, then $𝐟(1,𝐲)=𝐟(0,𝐲)+𝐡(\alpha (0),𝐲,𝐟(\alpha (0),𝐲))$. More generally, for all $x$ and $𝐲$: $𝐟(x,𝐲)=𝐟(x-1,𝐲)+\mathrm{\Delta }\left(\mathrm{\ell }(x-1)\right)\times 𝐡(x-1,𝐲,𝐟(x-1,𝐲))=𝐟(\alpha (\mathrm{\ell }(x)-1),𝐲)+𝐡(\alpha (\mathrm{\ell }(x)-1),𝐲,𝐟(\alpha (\mathrm{\ell }(x)-1),𝐲))$, where $\mathrm{\Delta }(\mathrm{\ell }(t-1))=\mathrm{\ell }(t)-\mathrm{\ell }(t-1)$. Starting from $t=x\ge 1$ and taking successive decreasing values of $t$, the first difference such that $\mathrm{\Delta }(t)\ne 0$ is given by the biggest $t-1$ such that $\mathrm{\ell }(t-1)=\mathrm{\ell }(x)-1$, i.e. $t-1=\alpha (\mathrm{\ell }(x)-1)$. Setting $𝐡(\alpha (-1),𝐲,\cdot )=𝐟(0,𝐲)$, it follows by induction that:

In the present paper, both polynomial expressions (see [3]) and limited polynomial expressions are considered. Let $\mathrm{𝗌𝗀}:\mathbb{Z}\to \mathbb{Z}$ be the sign function over $\mathbb{Z}$, taking value 1 for $x>0$ and 0 otherwise, and $\mathrm{𝖼𝗈𝗌𝗀}:\mathbb{Z}\to \mathbb{Z}$ be the cosign function, such that $\mathrm{𝖼𝗈𝗌𝗀}(x)=1-\mathrm{𝗌𝗀}(x)$.

To define the notion of degree for polynomial expressions, we follow the generalization to sets of variables introduced in [3].

A $\mathrm{𝗌𝗀}$-polynomial expression $P$ is said to be essentially constant in a set of variables $𝐱$ when $\mathrm{deg}(𝐱,P)=0$ and essentially linear in $𝐱$, when $\mathrm{deg}(𝐱,P)=1$.

The concept of linearity allows us to control the growth of functions defined by ODEs. In what follows, we will consider functions $𝐟:{\mathbb{N}}^{p+1}\to {\mathbb{Z}}^d$, i.e. vectors of functions $𝐟=f_1,\mathrm{\dots },f_d$ from ${\mathbb{N}}^{p+1}$ to $\mathbb{Z}$, and introduce the linear $\mathrm{\ell }$-ODE schema.

If $𝐮$ is essentially linear in $𝐟(x,𝐲)$, there exist matrices $𝐀$ and $𝐁$, whose coefficients are essentially constant in $𝐟(x,𝐲)$, such that $𝐟(0,𝐲)=𝐠(𝐲)$ and:

Then, for all $x$ and $𝐲$, $𝐟(x,𝐲)$ is

with the convention that ${\prod }_x^{x-1}\kappa (x)=1$ and $(\alpha (-1),𝐲,\cdot ,\cdot )=𝐟(0,𝐲)$. Actually, the use of matrices is not necessary for the scope of this paper, but it is consistent with the general presentation of computation through essentially linear ODEs, of which full details can be found in [10, 11].

One of the main results of [10] is the implicit characterization of $\mathrm{𝐅𝐏}$ by the algebra made of basic functions $\mathrm{𝟢},\mathrm{𝟣},{\pi }_i^p,\mathrm{\ell },+,-,\times ,\mathrm{𝗌𝗀}$ (where ${\pi }_i^p$ denotes the projection function) and closed under composition ($\circ$) and $\mathrm{\ell }$-ODE.

Boolean circuits are vertex-labeled directed acyclic graphs whose nodes/gates are either input nodes, output nodes or are labeled with a Boolean function from the set $\{\wedge ,\vee ,\neg \}$. Boolean circuit with modulo gates allows in addition gates labeled Mod 2 or, more generally, Mod $p$, that output the sum of the inputs modulo $2$ or $p$, respectively. Finally, Boolean circuit with majority gates are unbounded fan-in circuits including Maj gates, that output 1 when the majority of the inputs are 1’s. A family of circuits is $\mathrm{𝐃𝐥𝐨𝐠𝐭𝐢𝐦𝐞}$-uniform if there is a Turing machine (with a random access tape) that decides in deterministic logarithmic time the direct connection language of the circuit, i.e. which, given 1${}_{}{}^n,a,b$ and $t\in \{\wedge ,\vee ,\neg \}$, decides if $a$ is of type $t$ and $b$ is a predecessor of $a$ in the circuit (and analogously for input/output nodes). When dealing with circuits, the resources of interests are size, i.e. the number of gates, and depth, i.e. the length of the longest path from input to output (see [34] for further details and related results).

It is known that unbounded (poly$(n)$) fan-in can be simulated using a bounded tree of depth $O($log $n)$, so that ${\mathrm{𝐅𝐍𝐂}}^i\subseteq {\mathrm{𝐅𝐀𝐂}}^i\subseteq {\mathrm{𝐅𝐍𝐂}}^{i+1}$. However, the inclusion has been proved to be strict only for $i=0$. In contrast, when dealing with classes with counting ability, interesting bounds have been established.

We can even consider other levels in the $\mathrm{𝐅𝐓𝐂}$ hierarchy, such that for $i\in \mathbb{N}$, ${\mathrm{𝐅𝐓𝐂}}^i$ corresponds to classes of functions computed by families of unbounded fan-in circuits with Maj gates, of polynomial size and depth $O$((log $n){}^i$). It is known that the inclusion ${\mathrm{𝐅𝐀𝐂}}^0\subset \mathrm{𝐅𝐀𝐂𝐂}[\mathrm{𝟐}]$ is proper, as the parity function cannot be computed in constant depth by standard unbounded fan-in Boolean gates, but it can be if Mod 2 gates are added. Moreover, since any Mod $p$ gate can be expressed by Maj, $\mathrm{𝐅𝐀𝐂𝐂}[𝐩]\subset {\mathrm{𝐅𝐓𝐂}}^0$.

As mentioned, Cobham’s work paved the way to several recursion-theoretic characterizations for classes other than $\mathrm{𝐅𝐏}$, including small circuit ones. In 1988/90, Clote introduced the algebra ${𝒜}_0$ to capture functions in the log-time hierarchy (equivalent to ${\mathrm{𝐅𝐀𝐂}}^0$) using so-called concatenation recursion on notation (CRN) [12, 13]. The greater classes ${\mathrm{𝐅𝐀𝐂}}^i$ and $\mathrm{𝐅𝐍𝐂}$ are captured adding weak bounded recursion on notation [13], while ${\mathrm{𝐅𝐍𝐂}}^1$ has been characterized both in terms of the $k$-bounded recursion on notation ($k$-BRN) schema [14] and relying on the basic function $tree$ [13]. In 1990, an alternative algebra (and logic), based on a schema called upward tree recursion, was introduced to characterize ${\mathrm{𝐅𝐍𝐂}}^1$ [19]. In 1991, a new recursion-theoretic characterization (and arithmetic à la Buss) for $\mathrm{𝐅𝐍𝐂}$ was presented [1]. In 1992 and 1995, other small circuit classes, including ${\mathrm{𝐅𝐓𝐂}}^0$, were considered (and re-considered) by Clote and Takeuti, who also introduced bounded theories for them [16, 17]. More recently, characterizations for ${\mathrm{𝐅𝐍𝐂}}^i$ were developed in [9], this time following the ramification approach. In [3], the first ODE-based characterizations for ${\mathrm{𝐅𝐀𝐂}}^0$ and ${\mathrm{𝐅𝐓𝐂}}^0$ were introduced. Related approaches to capture small circuit classes have also been provided in the framework of model- and proof-theory, both in the first and second order [26, 5, 24, 31, 19, 1, 16, 17, 27, 21, 4, 20, 22]. To the best of our knowledge, so far, no uniform implicit framework to characterize these classes has been offered in the literature.

We start by revising the characterization of ${\mathrm{𝐅𝐀𝐂}}^0$ from [3]. Recall that the function algebra $𝔸ℂ𝔻𝕃$ capturing ${\mathrm{𝐅𝐀𝐂}}^0$ is based on the two very restrictive forms of $\mathrm{\ell }$-ODE’s below.

Relying on them, in [3], the ODE-based function algebra below is introduced:

where, as standard, $x\mathrm{\#}y=2^{\mathrm{\ell }(x)\times \mathrm{\ell }(y)}$. In the same paper, this class is shown to precisely characterize ${\mathrm{𝐅𝐀𝐂}}^0$, see [3, Cor. 19]. Here, we dramatically simplify the (indirect) completeness proof, by showing that $\mathrm{\ell }$-ODE₃ precisely captures the idea of looking for the value of a bit in an $\mathrm{\ell }(x)$ long sequence, while $\mathrm{\ell }$-ODE₁ corresponds to the idea of left-shifting (the binary representation of) a given number, possibly adding 1.

By weakening the constraints on linearity of the schemas which define ${\mathrm{𝐅𝐀𝐂}}^0$, we introduce an $\mathrm{\ell }$-ODE the computation of which is provably in $\mathrm{𝐅𝐀𝐂𝐂}[\mathrm{𝟐}]$ and actually characterizes this class. We consider a non-strict schema such that $A=-1$ and $B=K\in \{0,1\}$. As we will see (Section 4.4), this is a special case of the schema we will introduce to capture ${\mathrm{𝐅𝐍𝐂}}^1$. Together with the functions and schemas defining $𝔸ℂ𝔻𝕃$, it is also enough to capture $\mathrm{𝐅𝐀𝐂𝐂}[\mathrm{𝟐}]$, thus providing the very first ODE-based characterization for this small circuit class “with counters”.

Notably, this schema allows us to capture the computation performed by Mod 2 gates and to rewrite the parity function in a very natural way.

Notice that this example shows that $\mathrm{\ell }{\text{-b}}_0\text{ODE}$ really increases the power of $\mathrm{\ell }$-ODE₁, as the parity function is known not to be in ${\mathrm{𝐅𝐀𝐂}}^0$ (see [23]). This also indicates that $\mathrm{\ell }{\text{-b}}_0\text{ODE}$ is actually a schema capturing the specific computational power corresponding to $\mathrm{𝐅𝐀𝐂𝐂}[\mathrm{𝟐}]$. Moreover, it is shown that the desired closure property holds for it.

In this section, we introduce schemas the computation of which is proved to be in ${\mathrm{𝐅𝐓𝐂}}^0$. One is defined in terms of strict linear $\mathrm{\ell }$-ODE and provides a new, compact characterization for this class. The second couple of schemas considered are not strict, as they include simple calls to $f(x,𝐲)$, and are defined uniformly with respect to corresponding (i.e., non-strict) schemas for ${\mathrm{𝐅𝐀𝐂}}^0$ and $\mathrm{𝐅𝐀𝐂𝐂}[\mathrm{𝟐}]$ (as well as for ${\mathrm{𝐅𝐍𝐂}}^1$ and ${\mathrm{𝐅𝐀𝐂}}^1$, see Sections 4.4 and 4.5)

We start by dealing with the linear ODE schema defined deriving along $\mathrm{\ell }$ and so that $A(x,𝐲)$ and $B(x,𝐲)$ are both $\mathrm{𝗌𝗀}$-polynomial expressions, with no call to $f(x,𝐲)$.

This compactly encapsulates not only iterated multiplication and addition but also $\mathrm{\ell }$-ODE₁ and $\mathrm{\ell }$-ODE₃ computation.

These examples are especially relevant as they reveal that $\mathrm{\ell }\text{-pODE}$ is really more expressive than all strict schemas introduced so far (BCount is not computable in ${\mathrm{𝐅𝐀𝐂}}^0$ and $\mathrm{𝐅𝐀𝐂𝐂}[\mathrm{𝟐}]$, see [32, 33]). The closure property can be shown to hold for $\mathrm{\ell }\text{-pODE}$ by relying on the following result.