Functional characterizations of uniform log-depth and polylog-depth circuit families
Stephen Bloch · 2003
The classes of functions computable by uniform log-depth (NC/sup 1/) and polylog-depth circuit families are characterized as closures of a set of base functions. (The former is equivalent to ALOGTIME, the latter to polylogarithmic space.) The closures involve the 'safe' composition of S. Bellantoni and S. Cook (1992) as well as a safe divide-and-conquer recursion: a simple change to the definition of the latter distinguishes between log and polylog depth. The proofs proceed, in one direction, by showing that safe composition and divide-and-conquer recursion preserve growth rate and circuit depth bounds, and in the other, by simulating alternating Turing machines with divide-and-conquer recursion.>