Recursion schemata for slowly growing depth circuit classes (Q1764156)

The author investigates iterated log depth circuit classes. The article begins with an overview of the results obtained in this as well as in closely related fields up to \textit{A. Grzegorczyk} [``Some classes of recursive functions'', Rozprawy Mat. 4 (1953; Zbl 0052.24902)]. The author defines a class of basic functions, \(\text{BASE}_{i}\), containing the 0-ary constant 0, projection functions, two successors \(x\rightarrow 2x\) and \(x\rightarrow 2x+1\), as well as bit operating functions \(| x| =\left\lceil \log _{2}(x+1)\right\rceil\), \(\text{Bit}(x,i)=\left\lfloor x/2^{i}\right\rfloor \text{mod}\, 2\), \(x\#y=2^{| x| \cdot | y| }\), \(\text{MSP}(x,y)=\left\lfloor x/2^{| y| }\right\rfloor\). For \(i\geq 1\), the class \(\text{LD}^{i}\) is defined as the class of functions which are computable by \(n^{O(1)}\) size, \((\log ^{(i)}n)^{O(1)}\) depth circuits over the base \(\{(\wedge _{n})_{n\in \omega },(\vee_{n})_{n\in \omega },\lnot \}\). For \(i\geq 1\), the class \(\text{ND}^{i}\) is defined as the class of functions which are computable by \(n^{O(1)}\) size, \((\log ^{(i)}n)^{O(1)}\) depth circuits over the base \(\{(\wedge _{2}),(\vee _{2}),\lnot \}\). A circuit family is \(\text{END}^{i}\) if there exists a constant \(c\) such that the \(n\)-th circuit in the family has size \(n^{O(1)}\), depth \((\log ^{(i)}n)^{O(1)}\), and at most \(c\) levels of arbitrary fan-in AND and OR gates, the remaining levels being built from \(\wedge _{2}\), \(\vee _{2}\) and \(\lnot\) gates. The author proves that for all \(i\geq 2\) the following inclusions take place: \(\text{AC}^{0}\subseteq \text{LD}^{i}\subseteq \text{AC}^{1}\), as well as the same when replacing \(\text{LD}^{i}\) by \(\text{END}^{i}\). \textit{P. Clote} defined the notion of Concatenation Recursion on Notation (CRN) [``Sequential, machine-independent characterizations of the parallel complexity classes AlogTIME, \(\text{AC}^k\), \(\text{NC}^k\) and \text{NC}'', in: Feasible mathematics. Prog. Comput. Sci. Appl. Log. 9, 49--69 (1990; Zbl 0765.68034)]. Let \(i\)-WBRN be \textit{A. Cobham}'s [``The intrinsic computational difficulty of functions'', in: Logic Methodology Philos. Sci., Proc. 1964 Internat. Congr. 24--30 (1965; Zbl 0192.08702)] \(i\)-Weak Bounded Recursion on Notation. The author proves (Theorem 3.2) that \(U_{E^*}\)-uniform \(\text{LD}^{i}\) is the smallest class containing \(\text{BASE}_i\) and closed under composition, CR and \(i\)-WBRN operations. Using bases different from \(\text{BASE}_{i}\), the author proves an exact characterization of the class \(\text{END}^{i}\) (Theorem 4.4). The article contains also other results. Some open directions in the field are sketched.