Functional Characterizations of Uniform Log-depth and Polylog-depth Circuit Families

Stephen Bloch ^{∗} Department of Mathematics

University of California, San Diego La Jolla, CA 92093

Abstract

We characterize the classes of functions computable by uniform log-depth (NC^{1}) and polylog-depth circuit families 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 Bellantoni and Cook 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 divideand-conquer recursion preserve growth rate and circuit depth bounds, and in the other, by simulating alternating Turing machines with divide-and-conquer recursion.

1 Introduction

Much of the history of the study of polynomialtime computability has been informed by Cobham’s elegant characterization in [9] of the polynomial-time functions as the closure of certain simple functions under composition and a form of recursion. Specifically, Cobham’s “bounded recursion on notation” iterates a number of times equal not to the integer value of some parameter x, but rather to |x|, the length of x when written in binary notation, and also requires that the function computed by such recursion grow no faster than some pre-existing function, i.e. no faster than some function defined by composition of base functions alone. This bounding requirement effectively obliges anyone using bounded recursion on notation to accompany every use thereof with a proof that the function so defined has only polynomial growth rate.

Bellantoni and Cook, in [3], present an alternative characterization of polynomial-time-computable functions which omits the bounding requirement and instead distinguishes syntactically between “normal” function parameters and “safe” ones, on which a restricted set of operations are permitted. Most importantly, recursion is permitted only on “normal” parameters, while each step of that recursion must treat the results of previous steps as safe. Thus the function iterated at each step can be computed in time and space bounds depending only on x, not on the recursive definition. As a result, the size bounds on functions hold automatically rather than being a separate and inconvenient stipulation in the recursion scheme.

Other researchers have used similar techniques to Cobham’s to describe space-bounded and parallel complexity classes such as NC^{1}, which comprises problems solvable by log-depth, constant-fanin Boolean circuits and which is equivalent to O(log) time on an alternating Turing machine; NC, the problems solvable by polylog-depth, polynomial-size circuits; and AC^{k}, the problems solvable by log^{k}-depth, polynomial-size, polynomial-fanin circuits. Lind, in [11], gave a characterization of logspace, and Allen [1] a characterization of NC, both (like Cobham) explicitly bounding the growth rates of functions defined in their systems. Compton and LaFlamme [10] present a functional characterization of uniform NC^{1}, relying on a polynomial size bound implicit in their finitemodels approach. Clote, in [7], introduced a scheme of concatenation recursion on notation that corresponds to computing each bit of a function in parallel, and characterized uniform NC^{1} by combining concatenation recursion on notation with a somewhat unnatural tree-evaluation function. A more elegant characterization, in [8], replaces the tree-evaluation function by Cobham-style recursion on notation with a constant (rather than polynomial) bound.

By combining Bellantoni & Cook’s “safe parameters” technique with Allen’s “divide and conquer” recursion, we have avoided both explicit size bounds and unnatural base functions, and characterized both alternating log time (ALOGTIME, or uniform NC^{1}) and alternating polylog time (or uniform polylogdepth circuits, or polylog space). In addition, the close similarity between these two characterizations may shed light on the difference between the corresponding complexity classes.

∗This work was begun while the author attended the 1991 Conference on Proof Theory, Complexity and Arithmetic, supported by NSF/ČSAV grant INT- 8914569. Further work was supported by grants from the University of Manitoba.

Section 2 defines the terminology, recursion schemes, and functions used in this paper. Section 3 states and proves the characterization of NC^{1}; most of this section is concerned with simulating the computation of a machine within our function algebra. Section 4 states and proves the similar characterization of functions computable by uniform log^{O(1)}-depth circuits. Finally, Section 5 compares our methods with previous ones and discusses directions for further research.

2 Definitions

We shall think of our data not as natural numbers but primarily as finite strings over the alphabet Σ = {0, 1}. Such strings will however often be interpreted as binary numbers, treating the rightmost symbol as least significant; by convention, the rightmost symbol of a string will be called bit 0, the second-rightmost bit 1, and so on. We use the symbol λ to denote the empty string.

We define, not within the system but purely for notational convenience, the following functions:

|x| = the number of bits in a string x, or

⌈log(x + 1)⌉when thinking of x as a number

Bit(i, x) = the bit in position i of x,

treating i as a number

We’ll also frequently use ⌈log(x)⌉, which has the useful property that whenever x > 1, ⌈log(⌈x/2⌉)⌉ = ⌈log(x)⌉ − 1.

We now define a set of base functions. Following [3], we shall distinguish between “normal” and “safe” parameters of a function by writing the function with all normal parameters first, separated by a semicolon from the safe parameters, e.g. f(x, y; z).

Definition 1 Let BASE denote the following set of functions:

π_{k}^{i,j}(x_{1}, …, x_{i}; x_{i+1}, …, x_{i+j}) = x_{k},

the projection functions,

λ, 0, 1  constants
MSP (; x, y) = the leftmost |x| −^{.} |y| bits of x

(“most significant part”)

LSP (; x, y) = the rightmost |y| bits of x, with

|y| −^{.} |x| leading zeroes (“least significant part”)

Cond(; b, u, v) = \begin{cases}LSP (; u, max(u, v)) & if b is odd \\ LSP (; v, max(u, v)) & if b is even \end{cases}

(treating b as a number)

Conc(; x, y) = the concatenation of x and y
Bh(; x) = the rightmost ⌈|x|/2⌉ bits of x

(“back half”)

F h(; x) = the leftmost ⌊|x|/2⌋ bits of x

(“front half”)

Not(; x) = the one’s complement of x
Or(; x, y) = the bitwise OR of x and y,

with the length of the longer

Ins_{0}(; x) = x with a 0 inserted after each bit
Ins_{1}(; x) = x with a 1 inserted after each bit

Example: Ins_{0}(; 0110) = 00101000. Of course, Ins_{1}(; x) is redundant: it could be defined as Not(; Ins_{0}(; Not(; x))).

Note that each BASE function is defined in such a way that the length of the output is a simple function of the lengths of the inputs, to avoid worries about circuit uniformity. (This is the reason for the LSP ’s in the definition of Cond: the answer u or v is padded to a uniform length that will hold either.)

As we shall be using these BASE functions heavily, we shall often omit the semicolon from those that take only safe parameters for the sake of readability.

Definition 2 (Bellantoni & Cook) We say function f(x⃗; y⃗) is defined by safe composition from functions g(x_{1} … x_{r}; y_{1} … y_{s}), u_{1}(x⃗; ) … u_{r}(x⃗; ), and v_{1}(x⃗; y⃗) … v_{s}(x⃗; y⃗) if

f(x⃗; y⃗) = g(u_{1}(x⃗; ) … u_{r}(x⃗; ); v_{1}(x⃗; y⃗) … v_{s}(x⃗; y⃗)

Note that, according to this definition, a safe parameter to f can never be used as a normal parameter to any of the u’s or v’s, nor can it affect the normal parameters of g. However, a normal parameter to f can be passed into a safe position by using a projection function for one of the v’s. This “trap-door” effect will also be preserved by our recursion schemes.

Definition 3 (Bellantoni & Cook) A function f(z, x⃗; y⃗) is defined by safe recursion on notation from functions g(x⃗; y⃗), h_{0}(z, x⃗; u, y⃗), and h_{1}(z, x⃗; u, y⃗) if

f(0, x⃗; y⃗) = g(x⃗; y⃗)
f(s_{i}(z), x⃗; y⃗) = h_{i}(z, x⃗; f(z, x⃗; y⃗), y⃗)
for s_{i}(z) ≠ 0

where s_{i}(z) = 2z + i, for i = 0, 1.

When a function accepts a parameter as “safe” it effectively promises not to use that parameter to control the depth of a recursion. (So what is “safe” from the caller’s point of view might better be called “sensitive” from that of the called function.) All else being equal, then, a function which can make that promise is more powerful than one which cannot. For example, the concatenation function could be defined as Conc(x, y; ), Conc(x; y), or Conc(; x, y). Although all three compute exactly the same value, the third is the most flexible, and choosing it over the others to include in BASE will prove crucial in showing size and time bounds.

The major difference between the present system and that of [3] is the replacement of their scheme of “safe recursion on notation” by various forms of “safe divide-and-conquer recursion”. Divide-and-conquer recursion (splitting a large datum into two pieces of roughly equal size, and recursing on both) is familiar to every computer scientist, but to the author’s knowledge its first use to characterize a complexity class functionally was in [1], where the following scheme, which Allen calls “polynomial size branching recursion”, is used to build algebraic characterizations of logspace and NC. (A cosmetically different recursion scheme was called “limited recursion” in [4] and “upward tree recursion” in [10].)

Definition 4 (Allen, modified for our notation) A function f(y, x⃗) is defined by polynomial size branching recursion from functions g and h with polynomial size bound p(n) if

f(y, x⃗) = \{g(y, x⃗)  if |y| ≤ 1 ; {h(\begin{matrix}y, x⃗, \\ f(F h(y), x⃗), f(Bh(y), x⃗)) \end{matrix} \atop if |y| > 1}

and for all a, b⃗,

|f(a, b⃗)| ≤ p (|a| + ∑ |b⃗|)

We shall make similar definitions, but by distinguishing between normal and safe parameters we can dispense with the explicit size bound p.

Definition 5 A function f(z, b, x⃗; y⃗) is said to be defined by safe divide-and-conquer recursion (henceforth safe DCR) from functions g(z, x⃗; y⃗) and h(z, x⃗; u_{1}, u_{2}, y⃗) if

f(z, b, x⃗; y⃗) =

= \begin{cases}g(z, x⃗; y⃗) & if |z| ≤ max(|b|, 1) \\ h(\begin{matrix}z, x⃗; y⃗, \\ f(F h(; z), b, x⃗; y⃗), \\ f(Bh(; z), b, x⃗; y⃗)) \end{matrix} & if |z| > |b| \end{cases}

Note: One difficulty in “programming” with DCR is that each leaf of the binary computation tree computes the same function of (for the most part) the same data, distinguished only by the portion of z each is given. If the recursion were required to proceed until |z| ≤ 1, a more obvious definition, there could be only constantly many (i.e. |Σ| + 1) distinct leaf values in the whole tree, and we might expect safe DCR to define different classes of functions depending on the size of the alphabet. Specifying b, and hence when the recursion is to bottom out, allows leaves to be distinguished by larger data structures than a single bit, which appears necessary in order to prove the main theorems. We maximize |b| with 1 because if |b| = 0, the recursion goes into an infinite loop by repeatedly finding Bh(1) = 1. Example: Using safe DCR, we can define a function COP Y (x; y) which concatenates |x| copies of y (and hence has the same growth rate as the “smash” operator #, defined by x#y = 2^{|x|·|y|}). COP Y (x; y) =

= \begin{cases}λ & if |x| = 0 \\ y & if |x| = 1 \\ Conc(\begin{matrix}COP Y (F h(x); y), \\ COP Y (Bh(x); y)) \end{matrix} & if |x| > 1 \end{cases}

or more formally,

COP Y (x; y) = aux(x, 1; y)

aux(x, b; y) =

= \begin{cases}g(x; y) & if |x| ≤ max(|b|, 1) \\ Conc(; \begin{matrix}aux(F h(; x); y), \\ aux(Bh(; x); y)) \end{matrix} & if |x| > |b| \end{cases}

g(x; y) = Cond(; F h(; Conc(; 1, x)), y, λ)

The F h(; Conc(; 1, x)) in the definition of g allows us to distinguish between the cases |x| = 0 and |x| = 1. Aside from this, the formal definition is obvious and unilluminating; henceforth we shall usually give such definitions by DCR in the first, less formal manner.

Applying safe DCR to this in turn yields the following:

#_{3}(x, y; ) =
= \begin{cases}1 & if |x| = 0 \\ y & if |x| = 1 \\ COP Y (y; #_{3}(F h(x), y; )) & if |x| > 1 \end{cases}

This function has the property |#_{3}(x, y)| = |y|^{||x||}. This gives the above function the growth rate 2^{||x||·(||y||+O(1))}, effectively the same as that of the #_{3} operator defined by x#_{3}y = 2^{|x|#|y|}.

Definition 6 A function f(z, b, x⃗; y⃗) is defined by very safe DCR from functions g(z, x⃗; y⃗) and h(; z, x⃗, y⃗, u_{1}, u_{2}) if

f(z, b, x⃗; y⃗) =

= \begin{cases}g(z, x⃗; y⃗) & if |z| ≤ max(|b|, 1) \\ h(; \begin{matrix}z, x⃗, y⃗, \\ f(F h(; z), b, x⃗; y⃗), \\ f(Bh(; z), b, x⃗; y⃗)) \end{matrix} & if |z| > |b| \end{cases}

Note: This differs from safe DCR in that safe DCR allows the iterated function h to itself be defined by iteration, so long as said iteration does not depend on the results of previous calls to h; in very safe DCR, the iterated function takes no normal parameters whatsoever, and thus cannot be defined by iteration at all. For example, the above definition of COP Y is actually very safe, but the definition of #_{3} is not (in fact, we prove in Lemma 15 that #_{3} cannot be defined by very safe DCR).

Definition 7 sc(BASE), the “safe closure of BASE”, denotes the simultaneous closure of the BASE functions under safe composition and safe DCR.

Definition 8 vsc(BASE), the “very safe closure of BASE”, denotes the simultaneous closure of the BASE functions under safe composition and very safe DCR.

It is often useful to be able to combine a constant number of values into a tuple. If all the values x⃗ are guaranteed to be the same length, this can be easily done. Let Z be the string of zeroes of the same length as each of the x’s, then define a family of combining and extracting functions as follows:

Definition 9 COMB_{1}(; x) = x COMB_{2i}(; x_{1}, … x_{2i}) =

= Conc(\begin{matrix}COMB_{i}(; x_{1}, … x_{i}), \\ COMB_{i}(; x_{i+1}, … x_{2i})) \end{matrix}for i > 0

COMB_{2i+1}(; x_{1}, … x_{2i+1}) =

= Conc(\begin{matrix}COMB_{i}(; x_{1}, … x_{i+1}), \\ COMB_{i}(; x_{i+2}, … x_{2i+1}, Z)) \end{matrix}for i > 0

EXT R_{1}^{1}(; y) = y EXT R_{k}^{i}(; y) =

= \begin{cases}EXT R_{⌈k/2⌉}^{i}(; F h(y)) & if i ≤ ⌈k/2⌉ \\ EXT R_{⌈k/2⌉}^{i−⌈k/2⌉}(; Bh(y)) & if i > ⌈k/2⌉ \end{cases}

Thus EXT R_{k}^{i}(; COMB_{k}(; a_{1} … a_{k})) = a_{i} for all 1 ≤ i ≤ k.

Definition 10 A  collection  of  functions

f_{1}(z, b, x⃗; y⃗), … f_{k}(z, b, x⃗; y⃗) is said to be defined by simultaneous, safe divide-and-conquer recursion from functions h_{1}, … h_{k} and g_{1}, … g_{k} if for all i ≤ k,

f_{i}(z, b, x⃗; y⃗) =

= \begin{cases}g_{i}(z, x⃗; y⃗) \\ if |z| ≤ max(|b|, 1) \\ h_{i}(\begin{matrix}z, x⃗; y⃗, \\ f_{1}(F h(z), b, x⃗; y⃗) … f_{k}(F h(z), b, x⃗; y⃗), \\ f_{1}(Bh(z), b, x⃗; y⃗) … f_{k}(Bh(z), b, x⃗; y⃗)) \end{matrix} \\ if |z| > |b| \end{cases}

The definition of simultaneous, very safe divideand-conquer recursion is identical, except that all parameters to the h_{i}’s are treated as safe.

Lemma 11 If for all b, x⃗, y⃗, i, j we have |g_{i}(z, x⃗; y⃗)| = |g_{j}(z, x⃗; y⃗)| for |z| ≤ |b|, and if the equations (|u_{1}| = … = |u_{k}|) ∧ (|v_{1}| = … = |v_{k}|) imply |h_{i}(z, x⃗; y⃗, u⃗, v⃗)| = |h_{j}(z, x⃗; y⃗, u⃗, v⃗)|, and if g_{1} … g_{k}, h_{1} … h_{k} ∈ sc(BASE), and if functions f⃗ are defined by simultaneous, safe DCR from g⃗ and h⃗, then

f⃗ ⊆ sc(BASE)

That is, under these equal-length conditions, simultaneous safe DCR can be simulated by ordinary safe DCR.

A similar lemma holds for vsc(BASE).

Note: The equal-length hypothesis could be weakened considerably, but this form of the lemma is easy to prove, and suffices for our purposes. Proof for either sc(BASE) or vsc(BASE): The hypotheses of equal length, by an obvious induction, imply |f_{i}(z, b, x⃗; y⃗)| = |f_{j}(z, b, x⃗; y⃗)| for all z, b, x⃗, y⃗, i, j. Using the tuple-coding functions COMB and EXT R, we can define a single function F (z, b, x⃗; y⃗) as the encoding of the tuple f_{1}(z, b, x⃗; y⃗), … f_{k}(z, b, x⃗; y⃗). That is, given the value of a recursive call to F, we extract each f_{i} with EXT R_{k}^{i}, then apply the appropriate h’s and combine the results with COMB_{k}.

Many of the results herein concern circuit families. All circuit families in this paper are uniform in the strong, U_{E} sense of [12]: if the circuit family has size Z(n), the extended connection language of the circuits can be recognized by a deterministic Turing machine in time log(Z(n)). That is, paths in polynomial-sized circuits can be recognized in deterministic O(log(n)) time, and paths in 2polylog-sized circuits can be recognized in deterministic polylog time. Our circuits may contain gates computing the constants 0 and 1, negation, two-input AND, and two-input OR. Circuits that compute functions (as opposed to relations) are assumed to be multi-output.

Definition 12 If f(x⃗; y⃗) is a function with normal and safe inputs as specified, and a⃗ and b⃗ are suitable tuples of numbers, and A is an alternating algorithm that computes f’s bit-graph, then d_{A}[a⃗; b⃗] is the time, maximized over all i < |f(a⃗; b⃗)|, necessary to compute bit i of f(a⃗; b⃗) by alternating algorithm A.

Similarly, if F is a circuit family that computes f’s bit-graph, then d_{F} [a⃗; b⃗] is the depth, maximized over all bit positions i < |f(a⃗; b⃗)|, of the circuit applicable to inputs a⃗ and b⃗ and bit position i.

Again, if F is a multi-output circuit family that computes f, then d_{F} [a⃗; b⃗] is the depth of the circuit applicable to inputs a⃗ and b⃗. Note, in all these cases, that d[a⃗; b⃗] depends only on the lengths of a⃗ and b⃗, not on their values.

Definition 13 If f(x⃗; y⃗) is computable by uniform, polynomial-size, multi-output circuit family F, and there is a constant c such that for all a⃗, b⃗ we have d_{F} [a⃗; b⃗] ≤ c·max(log(|a⃗|, |b⃗|)), then we say f ∈ F NC^{1}.

Similarly, if there is a constant c such that for all a⃗, b⃗ we have d_{F} [a⃗; b⃗] ≤ c, then we say f ∈ F NC^{0}.

3 Characterizing Uniform NC^{1}

Theorem 14 The following are equivalent:

1. f(x⃗; ) ∈ vsc(BASE)

2. f(x⃗; ) ∈ F NC^{1}

3. the set {(i, b, x⃗)|Bit(i, f(x⃗; )) = b} is recognized by an alternating O(log)-time machine, and f has polynomial growth rate.

Proof : We first prove that (1) implies that f has polynomial growth rate (Lemma 15) and can be computed bitwise by log-depth, uniform circuits (Lemma 17); (2) follows from these two facts. The equivalence (2 ⟺ 3) is a result of Ruzzo [12]. And we prove (3 ⇒ 1) by simulating an arbitrary ALOG-TIME machine in vsc(BASE) (Lemma 19), then simulating polynomial-length comprehension (Lemma 23) to build the function f from its bit-graph.

Lemma 15 If f(x⃗; y⃗) ∈ vsc(BASE), then there is a polynomial p_{f} with nonnegative coefficients such that

|f(x⃗; y⃗)| ≤ p_{f}(|x⃗|) · max(|y⃗|, 1)

Note: The 1 is included to make things behave properly in case there are no “safe” parameters y⃗, or they’re all zero-length.

Corollary 16 If f(; y⃗) ∈ vsc(BASE), then f has linear growth rate.

This corollary is in fact the key to the proof, since the iterated function in very safe DCR must have no normal parameters: when a function of growth rate n ↦ kn is iterated log(|z|) times, the result has length k^{log(|z|)}n ≐ |z|^{log(k)}n, which is polynomial. Proof : The fastest-growing functions in BASE are Conc(; x, y), Ins_{0}(; x, y), and Ins_{1}(; x, y).

|Conc(; x, y)| = |x| + |y|
≤ 2 · max(|x|, |y|)

so they satisfy the statement of the Lemma with p_{f} ≡ 2; Ins_{0} and Ins_{1} are similar. All the remaining BASE functions have output no longer than their longest (safe) input, so p_{f} ≡ 1 will suffice for them. Definition by Safe Composition: Let f(x⃗; y⃗) = g(u(x⃗; ); v(x⃗; y⃗)), and suppose p_{g}, p_{u}, and p_{v} are polynomials satisfying Lemma 15 for functions g, u, and v respectively. Then

|f(x⃗; y⃗)| ≤ p_{g}(|u(x⃗; )|) · |v(x⃗; y⃗)|
≤ p_{g}(p_{u}(|x⃗|)) · p_{v}(|x⃗|) · max(|y⃗|, 1)

so it would suffice to let p_{f}(|x⃗|) = p_{g}(p_{u}(|x⃗|)) · p_{v}(|x⃗|). The proof for multiple functions u⃗ and v⃗ is similar.

Definition by Very Safe DCR: Let

f(z, b, x⃗; y⃗) = \begin{cases}g(z, x⃗; y⃗) & if |z| ≤ |b| \\ h(; \begin{matrix}z, x⃗, y⃗, \\ f(F h(z), b, x⃗; y⃗), \\ f(Bh(z), b, x⃗; y⃗)) \end{matrix} & if |z| > |b| \end{cases}

and suppose we know, by an inductive assumption, that (for some polynomial p_{g} and constant k_{h})

|g(z, x⃗; y⃗)| ≤ p_{g}(|z|, |x⃗|) · max(|y⃗|, 1)

and

|h(; z, x⃗, y⃗, u_{1}, u_{2})| ≤ k_{h} · max(|z|, |x⃗|, |y⃗|, |u_{1}|, |u_{2}|)

Then we prove, by induction on |z|, that

|f(z, b, x⃗; y⃗)| ≤

≤ k_{h}^{⌈log(|z|)⌉} · max(|z|, |b|, |x⃗|, p_{g}(|b|, |x⃗|) · max(|y⃗|))

Note that k_{h}^{⌈log(|z|)⌉} ≤ k_{h}^{log(|z|)+1} = k_{h} · |z|^{log(k_{h})} is polynomial in |z|, so the entire bound is polynomial in |z|, |b|, |x⃗| and linear in max(|y⃗|) as desired.

The base case, for |z| ≤ |b|, is obvious. For larger |z|, we know

|f(z, b, x⃗; y⃗)| ≤

≤ k_{h} · max(\begin{matrix}|z|, |x⃗|, |y⃗|, \\ |f(Bh(z), b, x⃗; y⃗)|, |f(F h(z), b, x⃗; y⃗)|) \end{matrix}

≤ k_{h} · max(|z|, |x⃗|, |y⃗|, k_{h}^{⌈log(⌈\frac{|z|}{2}⌉)⌉} ·

max(⌈\frac{|z|}{2}⌉ , |b|, |x⃗|, p_{g}(|b|, |x⃗|) · max(|y⃗|)))

≤ k_{h}^{1+⌈log(⌈|z|/2⌉)⌉} ·

max(|z|, |b|, |x⃗|, p_{g}(|b|, |x⃗|) · max(|y⃗|)) assuming p_{g}(|b|, |x⃗|) ≥ 1 (Note |z| ≥ 1 because we’re in the induction step, and k_{h} ≥ 1 because otherwise f has linear growth rate and we’re done)

= k_{h}^{1+⌈log(|z|)⌉−1} ·

max(|z|, |b|, |x⃗|, p_{g}(|b|, |x⃗|) · max(|y⃗|))

= k_{h}^{⌈log(|z|)⌉} · max(|z|, |b|, |x⃗|, p_{g}(|b|, |x⃗|) · max(|y⃗|))

as desired.

Lemma 17 If f(x⃗; y⃗) ∈ vsc(BASE), then there are constants k_{f} and c_{f} and a LOGTIME-uniform circuit family F computing the bit-graph of f with depth bound

d_{F} [x⃗; y⃗] ≤ k_{f} · max(||x⃗||) + c_{f}

Corollary 18 If f(; y⃗) ∈ vsc(BASE), then f can be computed by a LOGTIME-uniform family of constantdepth circuits; that is, it’s in F NC^{0}.

Again the corollary is in fact the key to the proof: when a function of constant circuit depth is iterated log(|z|) times, the result has depth O(log(|z|)). Proof : The BASE functions all have extremely simple circuits. The circuits for λ, 0, and 1 are in fact constant-valued, while the functions π_{k}^{i,j}, MSP, LSP, Conc, F h, Bh, Ins_{0}, and Ins_{1} can each be computed by wires routing inputs to outputs, with no gates at all. These are functions whose interesting dependency is entirely on the lengths of their inputs, which can be computed, added, subtracted, halved, and doubled by a random-access, log-time, deterministic machine. So all these functions have LOGTIME-uniform, constantdepth, bounded-fanin circuits. Cond, Or, and Not actually use some gates, but they too are clearly in F NC^{0}.

Definition by Safe Composition: Suppose f(x⃗; y⃗) = g(u(x⃗; ); v(x⃗; y⃗)). Suppose also that k_{g}, c_{g}, k_{u}, c_{u}, k_{v}, and c_{v} are constants satisfying Lemma 17 for circuit families G, U, and V. Finally, suppose (by Lemma 15) p_{u} is a polynomial such that |u(x⃗; )| ≤ p_{u}(|x⃗|). Since p_{u}(|x⃗|) is bounded by a monic polynomial in max(|x⃗|), we assume without loss of generality that it actually is one, i.e. p_{u}(|x⃗|) = a_{u} · max(|x⃗|)^{deg(p_{u})}.

Then

d_{F} [x⃗; y⃗] ≤

≤ d_{G}[u(x⃗; ); v(x⃗; y⃗)] + max(d_{U}[x⃗; ], d_{V} [x⃗; y⃗])
≤ k_{g} · ||u(x⃗; )|| + c_{g} +

max(k_{u} · max(||x⃗||) + c_{u}, k_{v} · max(||x⃗||) + c_{v})

≤ k_{g} · |a_{u} · max(|x⃗|)^{deg(p_{u})}| + c_{g} +

max(k_{u} · max(||x⃗||) + c_{u}, k_{v} · max(||x⃗||) + c_{v})

≤ k_{g} · deg(p_{u}) · max(||x⃗||) + |a_{u}| + c_{g} +
max(k_{u}, k_{v}) · max(||x⃗||) + max(c_{u}, c_{v})
≤ (k_{g} · deg(p_{u}) + max(k_{u}, k_{v})) · max(||x⃗||) +
max(c_{u}, c_{v}) + |a_{u}| + c_{g}

which is, as desired, linear in max(||x⃗||). As before, the proof in the case that there are multiple functions u⃗ and v⃗ is similar.

Definition by Very Safe DCR: Suppose

f(z, b, x⃗; y⃗) =

= \{g(z, x⃗; y⃗)  if |z| ≤ max(|b|, 1) ; {h(; \begin{matrix}z, x⃗, y⃗, \\ f(F h(z), b, x⃗; y⃗), \\ f(Bh(z), b, x⃗; y⃗)) \end{matrix} \atop if |z| > |b|}

and that k_{g}, c_{g}, and c_{h} satisfy the present lemma for circuit families G and H computing g and h respectively. Let F denote the obvious circuit family for f: an instance of circuit H, replacing each of its inputs by either a smaller instance of F or an instance of G, depending on whether |z| > |b|. Then for |z| > |b|,

d_{f}[z, b, x⃗; y⃗] ≤

≤ d_{H}[; z, x⃗, y⃗, f(F h(z), b, x⃗; y⃗), f(Bh(z), b, x⃗; y⃗)] +

d_{F} [Bh(z), b, x⃗; y⃗]

≤ c_{h} + d_{F} [Bh(z), b, x⃗; y⃗]
≤ ||z|| · c_{h} + d_{G}[z, x⃗; y⃗]
≤ ||z|| · c_{h} + k_{g} · max(||z||, ||x⃗||) + c_{g}
≤ (c_{h} + k_{g}) · max(||z||, ||x⃗||) + c_{g}

Thus each bit of f(x⃗; y⃗) can be computed in log depth (and therefore polynomial size). Since there are only polynomially many bits of output, the whole value of f can be computed by NC^{1} circuits. This proves one direction of Theorem 14.

Lemma 19 Given an alternating Turing machine M with inputs X⃗ and an O(log(|X⃗|)) time bound, there is a function f(X⃗; ) ∈ vsc(BASE) such that

f(X⃗; ) = \begin{cases}1 & if M accepts X⃗ \\ 0 & if M rejects X⃗ \end{cases}

In other words, vsc(BASE) can simulate the computation of an arbitrary ALOGTIME machine.

The proof of this lemma is algorithmic and fairly technical, and takes up most of the rest of Section 3. Proof of Lemma 19: We start by defining a number of utility functions to manipulate strings. The first is

ZEROES(; x) = LSP (; λ, x)

which returns a string of zeroes of the same length as x.

Next we define

P ADRT (; x, y) = Conc(x, ZEROES(; MSP (y, x)))

which pads its argument x on the right with zeroes to length max(|x|, |y|).

We frequently wish to get at the leftmost or rightmost bit of a string.

LOBIT (; x) = LSP (; x, 1)
DELLOBIT (; x) = MSP (x, 1)
HIBIT (; x) = MSP (x, MSP (x, 1))
DELHIBIT (; x) = LSP (; x, MSP (x, 1))

We also define a function to shift a number without changing its length.

SHL(; x, y) = LSP (Conc(x, y), x)

shifts x left by appending y, discarding the high bits so the result is the same length as x.

We would also like to be able to find the length of a string.

Len(x; ) = \begin{cases}λ & if |x| = 0 \\ 1 & if |x| = 1 \\ Conc(Len(F h(x); ), 1) & if |x| > 1 \end{cases}

returns a string y such that |y| = ||x||. Note that Len(x; ) does not return a binary representation of |x| itself.

Since a log-time Turing machine is defined with random access to its read-only input tape, we need a function to implement random access. We define GET BIT (X; i) to return bit i of the normal parameter X, treating i as a binary number. By convention, if |i| > log(|X|) we shall only pay attention to the low log(|X|) bits of i, while if |i| < log(|X|) we pad i on the left with zeroes. We also assume |X| is a power of 2. The function is defined by simultaneous, very safe DCR: let GET BIT (X; i) = f_{1}(X; X, LSP (i, DELLOBIT (; Len(X; )))) where

f_{1}(Y; X, i) =

= \begin{cases}X if Y ≤ 1 \\ F h(f_{1}(F h(Y); X, i)) \\ if Y > 1 and HIBIT (; f_{2}(F h(Y); X, i)) = 1 \\ Bh(f_{1}(F h(Y); X, i)) \\ if Y > 1 and HIBIT (; f_{2}(F h(Y); X, i)) = 0 \end{cases}

f_{2}(Y; X, i) =

= \begin{cases}P ADRT (; i, X) & if |Y | ≤ 1 \\ SHL(; F h(f_{2}(F h(Y); X, i))), 1) & if |Y | > 1 \end{cases}

Note that |X| = |P ADRT (; i, X)|, so the equallength requirement is met at the base level. It is also easily proven by induction that |f_{1}(Y; X, i)| = \frac{|X|}{|Y |} is a power of 2 for all X, Y that arise in the recursion. In particular, |f_{1}(F h(Y); X, i)| is always even, so if |f_{1}(F h(Y); X, i)| = |f_{2}(F h(Y); X, i)| then the lengths of F h(f_{1}(F h(Y); X, i)), Bh(f_{1}(F h(Y); X, i)), and SHL(; F h(f_{2}(F h(Y); X, i)), 1) are all equal. Thus this definition meets all the equal-length criteria of Lemma 11, and so GET BIT ∈ vsc(BASE).

As for its correctness, the GET BIT function first coerces i to length log(|X|) = ||X|| − 1, discarding high bits if i is too long and left-padding with zeroes if it’s too short, and then goes into the simultaneous recursion. At each step on the way up, the high bit of i determines whether to keep the front or back half of X; the other half is discarded, as is the high bit of i. By the time the functions return, i has been reduced to nothing and X to a single bit, which is the answer.

Now that these general-purpose utility functions are defined, we turn our attention to the particular machine we wish to simulate. We assume without loss of generality that all computation paths in the machine are the same length, that the configurations of the machine form layers strictly alternating between universal and existential states (say, the last non-leaf layer is existential), that each non-leaf configuration has exactly two successor configurations, and that access to the input tapes is only at leaf configurations. These assumptions increase the alternating time by only a constant factor.

Suppose we’re given an ALOGTIME machine M with j random-access input tapes and k work tapes, running in time bounded by t = d · max(||X⃗||), where X_{1} … X_{j} are the contents of the input tapes. Then

Definition 20 A configuration of M is a tuple (in the sense of Definition 9) ⟨q, IL_{1}, IR_{1}, … IL_{j}, IR_{j}, W L_{1}, W R_{1}, … W L_{k}, W R_{k}⟩ where

q represents finite state information,

IL_{i} represents the contents of index tape i to the left of the head, with the lowest-significance bits representing the squares closest to the head,

W L_{i} the contents of work tape i to the left of the head (similarly),

IR_{i} the contents of index tape i from the head rightwards (lowest-significance bits representing the square under the head), and

W R_{i} the contents of work tape i from the head rightwards (similarly).

Each element of the tuple is a string of length exactly t (assuming this is sufficient for the number of states).

Since the lengths of the elements are fixed and equal, they can all be encoded as described in Definition 9. Note that the inputs X⃗ are not an explicit part of a configuration.

We define BLOW UP (X⃗; ) to yield a string of length 2^{t} − 1 = 2^{d·max(||X⃗||)} − 1 ≐ max(|x⃗|)^{d}, so that ||BLOW UP (X⃗; )|| = d · max(||X⃗||) = t, by composing d invocations of the COP Y function and suitable numbers of Conc functions.

Define a function INIT_{M}(X⃗; ) to return the configuration comprising (an encoding of) the start state, j empty index tapes of length t, and k empty work tapes of the same size. This is clearly in vsc(BASE): we can compute Len(; BLOW UP (X⃗; )) to get something of length t, apply ZEROES to make it an empty tape, then form a tuple of finitely many such things and the start state with COMB.

Define two functions NEXT_{L} and NEXT_{R}, each taking a configuration and returning another, to correspond to the “left child” and “right child” of a given configuration. Note that the current state can be tested bit-by-bit by a finite composition of Cond and MSP functions, and a new state can be generated by concatenating constant functions. Similarly, the currently visible square of any tape can be extracted and tested with MSP and Cond, and tape head movement and writing can be easily done with MSP, Conc, and LSP. No recursion is used in the definitions of NEXT_{L} and NEXT_{R} so they can accept their configuration parameters as “safe”.

Next we’d like to build a binary tree of all the possible bit-strings of length t, to be used as paths from root to leaves. But for technical reasons we actually produce a tree not of paths but of “inflated paths”, in which the bits of interest appear in bit positions 0, 1, 3, 7, … 2^{t} − 1, and the bits in between are ignored. (Each of 2^{t} paths is inflated to length 2^{t}, so the tree has length 2^{2t}, which is still polynomial since t = O(||X⃗||).) Producing this binary tree, which must contain a different inflated path at each leaf, with bitwise-similar leaves near one another in the tree and with an easy mechanism for distinguishing universal branches from existential ones, is the most complex part of the proof.

Definition 21 If x is a bit-string, we define the deflation of x as the bit string y, of length ||x||, such that for all i < |y|, Bit(i, y) = Bit(2^{i} − 1, x). Conversely, we say any such x is an inflation of y. A string x is a full inflation of y if x is an inflation of y and |x| = 2^{|y|−1}.

The function that produces this binary tree of inflated paths is defined as follows:

P AT HS(x; ) = \begin{cases}λ & if |x| = 0 \\ 01 & if |x| = 1 \\ h(; P AT HS(Bh(x); )) & if |x| > 1 \end{cases}

where

h(; v) = \begin{cases}Conc(Ins_{0}(v), Ins_{1}(v)) \\ if HIBIT (; v) ≠ HIBIT (; Bh(v)) \\ Conc(Ins_{0}(v), Ins_{1}(Not(v))) \\ if HIBIT (; v) = HIBIT (; Bh(v)) \end{cases}

Clearly each iteration of h quadruples the length of the function, so if |x| is a power of 2,

|P AT HS(x; )| = 2 · 4^{log(|x|)} = 2|x|^{2}

The value of P AT HS(x; ) can be usefully interpreted as 2|x| blocks of length |x|. Indeed, it can be thought of as (the root of) a binary tree: define N_{k}^{i,x}, the k-th node of height i in P AT HS(x; ), to be bits k · 2^{i}|x| through (k + 1) · 2^{i}|x| − 1, as long as these numbers are less than 2|x|^{2}, the total number of bits. Then the nodes of height 0, the leaves, are the individual blocks of length |x| and the left and right children of any nonleaf node are its front and back halves. Furthermore, the following are all equivalent:

• N_{j}^{i,x} is a descendant of N_{j′}^{i′,x}

• j′2^{i′}|x| ≤ j2^{i}|x| < (j + 1)2^{i}|x| ≤ (j′ + 1)2^{i′}|x|

• j′2^{i′} ≤ j2^{i} < (j + 1)2^{i} ≤ (j′ + 1)2^{i′}

Note that this last inequality is independent of x.

The less obvious properties of P AT HS are presented in the following technical lemma. The notation ±x denotes “either x or Not(x)”.

Lemma 22 Let |x| be a power of 2 and i ≤ log(2|x|) = ||x||. Then

1. If |x| > 1, and if j ≥ ⌊|x|/2^{i}⌋, then N_{j}^{i,x} = Ins_{0}(N_{j−⌊|x|/2^{i}⌋}^{i,Bh(x)}) while if j < ⌊|x|/2^{i}⌋, then N_{j}^{i,x} = Ins_{1}(±N_{j−⌊|x|/2^{i}⌋}^{i,Bh(x)})

2. For any node in P AT HS(x; ) of height i > 0, the high bits of its two children are equal iff i is even.

3. The following are equivalent, for any two leaves N_{j_{1}}^{0,x} and N_{j_{2}}^{0,x} in P AT HS(x; ):

(a) The leaves have a common ancestor of height i.

(b) The leaves have the same rightmost ⌊|x|/2^{i}⌋ bits.

(c) The leaves’ deflations have the same rightmost ||x|| − i bits.

4. If P AT HS(x; ) is interpreted as a tree, its leaves comprise one full inflation of each path of length ||x||.

The proof of this lemma involves a number of straightforward but tedious inductions, and we omit it, but illustrate it by the following Example: P AT HS(λ; ) = λ, no blocks of length 0 P AT HS(1; ) = ˆ0ˆ1, 2 blocks of length 1

P AT HS(11; ) = \overbrace{00} \overbrace{10} \overbrace{01} \overbrace{11}, 4 blocks of length 2 P AT HS(1111; ) =

= \overbrace{0000} \overbrace{1000} \overbrace{0010} \overbrace{1010} \overbrace{1111} \overbrace{0111} \overbrace{1101} \overbrace{0101}, 8 blocks of length 4, each of which is the full inflation of a distinct 3-bit path. P AT HS(11111111; ) =

= \begin{matrix}\overbrace{00000000} & \overbrace{10000000} & \overbrace{00001000} & \overbrace{10001000} \\ \overbrace{10101010} & \overbrace{00101010} & \overbrace{10100010} & \overbrace{00100010} \\ \overbrace{01010101} & \overbrace{11010101} & \overbrace{01011101} & \overbrace{11011101} \\ \overbrace{11111111} \overbrace{01111111} \overbrace{11110111} \overbrace{01110111}, \end{matrix}

16 blocks of length 8, each of which is the full inflation of a distinct 4- bit path.

The reader may also verify the remaining properties in these examples.

Now, recalling that ||BLOW UP (X⃗; )|| = t, the time bound of the alternating machine, it follows that P AT HS(BLOW UP (X⃗; ); ) produces a binary tree of full inflations of all the possible length-t paths. Given one such path P and a starting configuration C, we must find the configuration reached by following that path.

NEXT (; P, C) = Cond(\begin{matrix}HIBIT (; P), \\ NEXT_{L}(; C), \\ NEXT_{R}(; C)) \end{matrix}

computes NEXT_{L} if the high bit of P is set, and otherwise NEXT_{R}. Recursion on this function yields

GET LEAF (P; C) =

= \begin{cases}NEXT (; P, C) \\ if |P | ≤ 1 \\ NEXT (; P, GET LEAF (Bh(P); C)) \\ otherwise \end{cases}

The GET LEAF function chops the inflated path in half repeatedly, each time extracting a single bit of path information (this is why the path was inflated in the first place) and finding a left or a right child according to that bit; when no path remains, i.e. after t choppings, it uses the root configuration C.

Next, having found our leaf configuration, we must decide whether it is an accepting configuration. This requires checking whether the state is an accepting state, a rejecting state, or a query state, and if the last, testing the appropriate bit of the appropriate input (using GET BIT on the “normal” input parameters X⃗). No recursion is required except that to define GET BIT, and we can define EV ALLEAF (X⃗; C).

Now we can define the {0, 1}-valued function EV ALT REE(T, s, X⃗; C) as follows (s is intended to be any fully-inflated path, i.e. |s| = 2^{t−1}):

EV ALT REE(T, s, X⃗; C) =

= \begin{cases}EV ALLEAF (X⃗; GET LEAF (T; C)) \\ if |T | ≤ |s| \\ EV ALT REE(F h(T), s, X⃗; C)∧ \\ EV ALT REE(Bh(T), s, X⃗; C) \\ if |T | > |s| and the height of T is odd \\ EV ALT REE(F h(T), s, X⃗; C)∨ \\ EV ALT REE(Bh(T), s, X⃗; C) \\ if |T | > |s| and the height of T is even \end{cases}

or, more formally,

EV ALT REE(T, s, X⃗; C) =

= \begin{cases}EV ALLEAF (X⃗; GET LEAF (T; C)) \\ if |T | ≤ |s| \\ h(\begin{matrix}; T, \\ EV ALT REE(F h(T), s, X⃗; C), \\ EV ALT REE(Bh(T), s, X⃗; C)) \end{matrix} \\ if |T | > |s| \end{cases}

where

h(; T, u_{1}, u_{2}) = Cond(; \begin{matrix}HIBIT (; T), \\ Cond(; \begin{matrix}HIBIT (; Bh(T)), \\ Cond(; u_{1}, 1, u_{2}), \\ Cond(; u_{1}, u_{2}, 0)), \end{matrix} \\ Cond(; \begin{matrix}HIBIT (; Bh(T)), \\ Cond(; u_{1}, u_{2}, 0), \\ Cond(; u_{1}, 1, u_{2}))) \end{matrix} \end{matrix}

Finally, |BLOW UP (X⃗; )| = 2^{t} − 1 and so |Bh(BLOW UP (X⃗; ))| = ⌈\frac{2^{t}−1}{2}⌉ = 2^{t−1}, so the simulation of the ATM can be accomplished by

SIMULAT E(X⃗; ) =

= EV ALT REE(\begin{matrix}P AT HS(BLOW UP (X⃗; ); ), \\ Bh(BLOW UP (X⃗; )), X⃗; \\ INIT_{M}(X⃗; )) \end{matrix}

Thus ALOGT IME ⊆ vsc(BASE). This completes the proof of Lemma 19.

Lemma 23 If F (x⃗; ) has exactly polynomial growth rate, and there is a function f(x⃗, i; ) ∈ vsc(BASE) such that

(∀i < |F (x⃗; )|)(f(x⃗, i; ) = Bit(i, F (x⃗; )))

then F (x⃗; ) ∈ vsc(BASE).

Proof of Lemma 23: We have already noted that any polynomial growth rate can be attained in vsc(BASE), so we can define a function SIZE_{F} such that |SIZE_{F} (x⃗; )| = |F (x⃗; )|. Now we build a binary tree, similar to P AT HS, each of whose leaves contains a different value, but this time the values are the binary numbers 0 … |SIZE_{F} (x⃗; )| − 1 in reverse order. We can then define F by very safe DCR on such a tree T as follows: F (x⃗; ) = F′(T, Len(SIZE_{F} (x⃗; ); ), x⃗; y⃗) F′(T, z, x⃗; ) =

= \begin{cases}f(T, x⃗; ) if |T | ≤ |z| \\ Conc(F′(F h(T), z, x⃗; ), F′(Bh(T), z, x⃗; )) \\ if |T | > |z| \end{cases}

The iterated function is Conc, which is associative; so the effect is simply to concatenate the bits f(|z|−1, x⃗; ), f(|z|−2, x⃗; ), … f(1, x⃗; ), f(0, x⃗; ), where the numbers |z| − 1, |z| − 2, … 1, 0 are given to f in binary. (Note that if F were allowed safe parameters, and they affected its length, SIZE_{F} would depend on those parameters, and therefore could not be used in a normal position in F′. This is why the F in this lemma only takes normal parameters; the lemma is somewhat weaker than we might like, but it suffices to prove Theorem 14.)

All that remains is to build, given a string z, a list of the numbers from 0 … |z| − 1 in binary, in reverse order. We define it by simultaneous, very safe DCR:

COUNT UP (z; ) = f_{2}(z; Len(z; ))

f_{1}(z; b) = \begin{cases}λ if |z| = 0 \\ SHL(; ZEROES(; b), 1) if |z| = 1 \\ Conc(\begin{matrix}SHL(; f_{1}(Bh(z); b), 0), \\ SHL(; f_{1}(Bh(z); b), 0)) \end{matrix} \\ if |z| > 1 \end{cases}

f_{2}(z; b) = \begin{cases}λ if |z| = 0 \\ ZEROES(; b) if |z| = 1 \\ Conc(\begin{matrix}Or(f_{1}(Bh(z); b), f_{2}(Bh(z); b)), \\ f_{2}(Bh(z); b)) \end{matrix} \\ if |z| > 1 \end{cases}

Clearly, |f_{1}| = |f_{2}| = |b| at the base level, and each of f_{1} and f_{2} exactly doubles in length at each recursive step, so this definition meets the requirements of Lemma 11.

As for how it works, f_{1}(z; b) is the concatenation of |z| identical blocks of length |b|, each composed of zeroes except for a 1 in bit position ||z|| − 1: shifting such a list of blocks left by one bit has the effect of shifting over the 1 in each block simultaneously. (All this is precisely correct only if |z| is a power of 2, which we shall assume henceforth.)

f_{2}(z; b) starts as a block of zeroes (for |z| = 1), and at each subsequent step two copies of it are concatenated, the first having a high bit set in each of its blocks by OR-ing with f_{1}(z; b). Thus if f_{2}(Bh(z); b) lists the binary numbers \frac{|z|}{2} − 1, … 1, 0 in blocks of size |b|, then f_{2}(z; b) lists |z| − 1, … \frac{|z|}{2} followed by \frac{|z|}{2} − 1, … 1, 0, i.e. |z| − 1, … 1, 0 as desired.

Plugging the resulting COUNT UP (z; ) in place of the T in the above definition of F completes the proof of the lemma. This comprehension capability allows us to pass from a function defined by its bit-graph (as produced by Lemma 19) to the function itself. In combination with Lemmas 15 and 17, this completes the proof of Theorem 14.

4 Characterizing Uniform Polylog Depth

Theorem 24 The following are equivalent:

1. f(x⃗; ) ∈ sc(BASE)

2. f(x⃗) can be computed from x⃗ by a LOGTIMEuniform, polylog depth circuit family, and f has 2^{poly(||x⃗||)} growth rate

3. the i-th bit of f(x⃗) can be computed from i and x⃗ in alternating polylog time, and f has 2^{poly(||x⃗||)} growth rate

4. f(x⃗) can be computed by a deterministic Turing machine in polylogarithmic space (not counting a write-only output tape)

The proof is similar to that of Theorem 14. We prove (1 ⇒ 2) and (3 ⇒ 1) directly. (2 ⟺ 3) is a result of Ruzzo [12]. (3 ⇒ 4) follows from a result of Borodin, quoted in [6] as Theorem 4.2. And (4 ⇒ 3) is easily proven by a technique similar to that of Savitch’s Theorem.

Lemma 25 If f(x⃗; y⃗) ∈ sc(BASE), then there is a polynomial p_{f} with nonnegative coefficients such that

|f(x⃗; y⃗)| ≤ 2^{p_{f} (||x⃗||)} · max(|y⃗|, 1)

Proof of Lemma 25: As pointed out before, all the BASE functions have linear growth rate, easily satisfying this criterion. Definition by Safe Composition: If f(x⃗; y⃗) is defined by safe composition as g(u(x⃗); v(x⃗; y⃗)), and if p_{g}, p_{u}, and p_{v} are polynomials satisfying the Lemma for functions g, u, and v respectively, then

|f(x⃗; y⃗)| ≤ 2^{p_{g}(||u(x⃗)||)} · |v(x⃗; y⃗)|
≤ 2^{p_{g}(|2^{pu(||x⃗||)}|)} · 2^{p_{v}(||x⃗||)} · max(|y⃗|, 1)
≤ 2^{p_{g}(p_{u}(||x⃗||)+1)} · 2^{p_{v}(||x⃗||)} · max(|y⃗|, 1)
≤ 2^{p_{g}(p_{u}(||x⃗||)+1)+p_{v}(||x⃗||)} · max(|y⃗|, 1)

so the statement is satisfied by letting

p_{f}(||x⃗||) = p_{g}(p_{u}(||x⃗||) + 1) + p_{v}(||x⃗||)

Definition by Safe DCR: On the other hand, if f(z, b, x⃗; y⃗) is defined by safe DCR on the parameter z, to wit:

f(z, b, x⃗; y⃗) =

= \begin{cases}g(z, x⃗; y⃗) \\ if |z| ≤ max(|b|, 1) \\ h(z, x⃗; f(F h(z), b, x⃗; y⃗), f(Bh(z), b, x⃗; y⃗), y⃗) \\ if |z| > |b| \end{cases}

and p_{g} and p_{h} are polynomials satisfying the Lemma for functions g and h respectively, then we prove by induction on |z| that

|f(z, b, x⃗; y⃗)| ≤

≤ 2^{⌈log(|z|)⌉·p_{h}(||z||,||x⃗||)+p_{g}(||b||,||x⃗||)} · max(|y⃗|, 1)

The base case, for |z| ≤ |b|, is obvious. For larger |z|, we know

|f(z, b, x⃗; y⃗)| ≤

≤ 2^{||z||,||x⃗||)} ·

max(|f(F h(z), b, x⃗; y⃗)|, |f(Bh(z), b, x⃗; y⃗)|, |y⃗|)

≤ 2^{p_{h}(||z||,||x⃗||)} ·
max (2^{⌈log(^{⌈^{\frac{|z|}{2}}⌉})⌉·p_{h}(|⌈\frac{|z|}{2}⌉|,||x⃗||)+p_{g}(||b||,||x⃗||)}, |y⃗|)
≤ 2^{p_{h}(||z||,||x⃗||)} ·
max (2^{(⌈log(|z|)⌉−1)·p_{h}(||z||,||x⃗||)+p_{g}(||b||,||x⃗||)}, |y⃗|)
≤ 2^{p_{h}(||z||,||x⃗||)} ·

2^{(⌈log(|z|)⌉−1)·p_{h}(||z||,||x⃗||)+p_{g}(||b||,||x⃗||)} · max(|y⃗|)

≤ 2^{⌈log(|z|)⌉·p_{h}(||z||,||x⃗||)+p_{g}(||b||,||x⃗||)} · max(|y⃗|)

as desired.

Lemma 26 If f(x⃗; y⃗) ∈ sc(BASE), then there is a polynomial q_{f} with nonnegative coefficients and a uniform circuit family F computing f’s bit-graph such that for all x⃗, y⃗,

d_{F} [x⃗; y⃗] ≤ q_{f}(||x⃗||) · max(||y⃗||, 1)

Proof of Lemma 26: All the BASE functions can obviously be computed in such a fashion. For the remaining cases, we assume wolog that d_{F} [a⃗; b⃗] and the like are monotone in the lengths of their arguments. Definition by Safe Composition: If f(x⃗; y⃗) is defined by safe composition as g(u(x⃗; ); v(x⃗; y⃗)), then let p_{g}, p_{u}, and p_{v} be polynomials whose exponentials bound the growth of g, u, and v respectively as in Lemma 25, and let q_{g}, q_{u}, and q_{v} be polynomials bounding the circuit depth required to compute g, u, and v with circuit families G, U, and V respectively, by an inductive hypothesis on the present lemma. And let F be the obvious circuits for f: a copy of circuit G, with each input replaced by a copy of circuit U or V as appropriate.

d_{F} [x⃗; y⃗] ≤

≤ d_{G}[u(x⃗; ); v(x⃗; y⃗)] + max(d_{U}[x⃗; ], d_{V} [x⃗; y⃗])
≤ q_{g}(||u(x⃗; )||) · ||v(x⃗; y⃗)|| +
max(q_{u}(||x⃗||), q_{v}(||x⃗||) · max(||y⃗||, 1))
≤ q_{g}(p_{u}(||x⃗||)) · max(p_{v}(||x⃗||) + max(||y⃗||, 1)) +
max(q_{u}(||x⃗||), q_{v}(||x⃗||) · max(||y⃗||, 1))
≤ q_{g}(p_{u}(||x⃗||)) · p_{v}(||x⃗||) · max(||y⃗||, 1) +
(q_{u}(||x⃗||) + q_{v}(||x⃗||)) · max(||y⃗||, 1)
= (q_{g}(p_{u}(||x⃗||)) · p_{v}(||x⃗||) + q_{u}(||x⃗||) + q_{v}(||x⃗||)) ·
max(||y⃗||, 1)

so the statement is satisfied by letting

q_{f}(r⃗) = q_{g}(p_{u}(r⃗)) · p_{v}(r⃗) + q_{u}(r⃗) + q_{v}(r⃗))

Again, the proof in the case that there are multiple functions u⃗ and v⃗ is similar.

Definition by Safe DCR: Now suppose f(z, b, x⃗; y⃗) is defined by safe DCR on the parameter z, to wit:

f(z, b, x⃗; y⃗) =

= \begin{cases}g(z, x⃗; y⃗) \\ if |z| ≤ |b| \\ h(z, x⃗; f(F h(z), b, x⃗; y⃗), f(Bh(z), b, x⃗; y⃗), y⃗) \\ if |z| > |b| \end{cases}

Let p_{f}, p_{g}, and p_{h} be polynomials satisfying Lemma 25 for functions f, g, and h respectively, and q_{g} and q_{h} be polynomials satisfying Lemma 26 for circuit families G and H. And let F be the obvious circuits for f: an instance of circuit H, but replacing each of its inputs by a smaller instance of F or an instance of G, depending on whether |z| > |b|.

We know that, for all |z′| ≤ |z|,

|f(z′, x⃗; y⃗)| ≤ 2^{p_{f} (||z||,||b||,||x⃗||)} · max(|y⃗|, 1) so if h(z, x⃗; u_{1}, u_{2}, y⃗) is called in the course of computing f(z, b, x⃗; y⃗), we can be assured that

|u_{1}|, |u_{2}| ≤ 2^{p_{f} (||z||,||b||,||x⃗||)} · max(|y⃗|, 1)

and therefore ||u_{1}|| and ||u_{2}|| are each at most p_{f}(||z||, ||b||, ||x⃗||) + max(||y⃗||, 1). With this in mind, then,

d_{F} [z, b, x⃗; y⃗] ≤

≤ \begin{matrix}max( d_{G}[z, x⃗; y⃗], \\ d_{H}[z, x⃗; f(F h(z), b, x⃗; y⃗), f(Bh(z), b, x⃗; y⃗)]+ \\ max(d_{F} [F h(z), b, x⃗; y⃗], d_{F} [Bh(z), b, x⃗; y⃗])) \end{matrix}

≤ \begin{matrix}max(d_{G}[z, x⃗; y⃗], \\ d_{H}[z, x⃗; f(F h(z), b, x⃗; y⃗), f(Bh(z), b, x⃗; y⃗), y⃗]+ \\ d_{F} [Bh(z), b, x⃗; y⃗]) \end{matrix}

by monotonicity of d_{F}

≤ \begin{matrix}d_{G}[z, x⃗; y⃗]+ \\ (∑_{i=||b||+1}^{||z||} q_{h}(i, ||x⃗||)) · \\ max(p_{f}(||z||, ||b||, ||x⃗||) + max(||y⃗||, 1), ||y⃗||) \end{matrix}

by the remarks above

≤ \begin{matrix}d_{G}[z, x⃗; y⃗] + ||z|| · q_{h}(||z||, ||x⃗||)· \\ (p_{f}(||z||, ||b||, ||x⃗||) + max(||y⃗||, 1)) \end{matrix}

by monotonicity of q_{h}

≤ \begin{matrix}q_{g}(||z||||x⃗||) · max(||y⃗||, 1) + ||z|| · q_{h}(||z||, ||x⃗||)· \\ (p_{f}(||z||, ||b||, ||x⃗||) + max(||y⃗||, 1)) \end{matrix}
≤ (\begin{matrix}||z|| · q_{h}(||z||, ||x⃗||) · (p_{f}(||z||, ||b||, ||x⃗||) + 1)+ \\ q_{g}(||z||, ||x⃗||)) · max(||y⃗||, 1) \end{matrix}

and so it would suffice to let q_{f}(||z||, ||b||, ||x⃗||) be

||z||·q_{h}(||z||, ||x⃗||)·(p_{f}(||z||, ||b||, ||x⃗||)+1)+q_{g}(||z||, ||x⃗||)

Thus each bit of f(x⃗; y⃗) can be computed in polylog depth, 2^{polylog} size. Since there are at most 2^{polylog} bits of output, the whole function value is computable by polylog-depth, 2^{polylog}-size circuits. This is one direction of Theorem 24.

For the remaining direction, we shall show that

Lemma 27 Given an alternating Turing machine M with inputs X⃗ and time bound polynomial in log(|X⃗|), there is a function f ∈ sc(BASE) such that

f(X⃗; ) = \begin{cases}1 & if M accepts X⃗ \\ 0 & if M rejects X⃗ \end{cases}

In other words, sc(BASE) can simulate the computation of an arbitrary polylog-time alternating machine.

The proof of this is almost identical to that of Lemma 19. The difference is that with merely-safe DCR we can define not only COP Y but #_{3}, and with this growth rate we can build and evaluate a binary tree of polylog rather than merely O(log) depth.

With #_{3} in hand, then, and given an alternating machine with time bound t = p_{M}(||X⃗||), we can redefine BLOW UP (X⃗; ) to have length 2^{p_{M} (||X⃗||)} − 1, and hence ||BLOW UP (X⃗; )|| ≥ p_{M}(||X⃗||), by composing deg(p_{M}) invocations of the #_{3} function as well as suitable numbers of COP Y and Conc functions.

We define the functions ZEROES, INIT_{M}, GET BIT, NEXT_{L}, NEXT_{R}, NEXT, P AT HS, EV ALLEAF, GET LEAF, EV ALT REE, and SIMULAT E exactly as before; the result is that EV ALT REE now evaluates an alternating and/or tree of depth p_{M}(||X⃗||) rather than d·max(||X⃗||), and thus correctly simulates the alternating polylog-time Turing machine.

Lemma 28 If F (x⃗; ) has growth rate 2^{p(||x⃗||)}, and there is a function f(x⃗, i; ) ∈ sc(BASE) such that (∀i < |F (x⃗; )|)(f(x⃗, i; ) = Bit(i, F (x⃗; ))), then F (x⃗; ) ∈ sc(BASE).

Proved exactly as Lemma 23, with larger growth rates.

5 Conclusions and Observations

The most unfamiliar functions in BASE are, of course, Ins_{0} and Ins_{1}, although they are in F NC^{0} and hence not computationally difficult. An alternate way to prove the theorems in this paper would be to omit them but add some form of concatenation recursion, analogous to Clote’s Concatenation Recursion on Notation (see [7]).

Our Theorem 14 bears a resemblance to Theorem 3.3 of [10], which first defines the “simple functions” as the closure of a few specific functions (similar to our BASE functions) under composition, and then characterizes ALOGTIME as the closure of the simple functions, together with an equality test, under composition and “upward tree recursion”, a scheme that allows branching iteration of any simple function. Our analogue of Compton & LaFlamme’s simple functions are all those functions with no normal parameters, a purely syntactic definition which we feel makes the recursion scheme’s definition cleaner. In addition, we need no a priori polynomial size bound, need not treat the equality test as a special case, and our bit-string formulation seems more natural than the finite-models formulation in that paper.

Theorem 24 can be seen as analogous to Theorem 2.1 of [1], which characterizes NC, circuits of simultaneous polylog depth and polynomial size. The reason Allen’s system describes NC while Theorem 24 describes polylog-depth circuits is simply that Allen’s recursion schemes involve an explicit polynomial size bound. ([1] actually gives both a recursiontheoretic and a proof- theoretic characterization of NC, the latter using the theory D^{1}, which is equivalent to the bounded arithmetic theory R_{2}^{1}. Buss, Krajíček, and Takeuti [5], by replacing R_{2}^{1} with R_{3}^{1}, have characterized polylog space proof-theoretically.) The present result also requires only two functioncombination schemes (safe composition and safe DCR) rather than the four (composition, p-comprehension, log-bounded recursion on notation, and polynomialbounded branching recursion) in [1], and uses simpler base functions.

The technique of distinguishing safe parameters pioneered in [3] has now been extended to characterize both polylog space and alternating log time, and has proven itself to be a clean, general idea. We speculate that further variants thereon may yield useful characterizations of log space, NC, NC^{k}, and other complexity classes. (Bellantoni, in [2], extends the characterization of P to the polynomial hierarchy. In recent personal communication he claims to have characterized logspace and NC in a similar manner, but the author has not seen the proofs.) In addition, these clean functional characterizations may provide techniques for developing new proof-theoretic characterizations in the style of [4].

References

[1] William Allen. Divide and Conquer as a Foundation of Arithmetic. PhD thesis, University of Hawaii at Manoa, 1988.

[2] Stephen Bellantoni. A new recursion-theoretic characterization of the functional polytime hierarchy. Manuscript, 1992.

[3] Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the polytime functions. computational complexity, 2:97– 110, Dec 1992.

[4] Samuel R. Buss. Bounded Arithmetic. PhD thesis, Princeton University, 1986.

[5] Samuel R. Buss, Jan Krajíček, and Gaisi Takeuti. Provably total functions in bounded arithmetic theories R_{3}^{i}, U_{2}^{i} and V_{2}^{i}. In P. Clote and J. Krajíček, editors, Arithmetic, Proof Theory and Computational Complexity, pages 116–161. Oxford University Press, 1993.

[6] A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28(1):114–133, January 1981.

[7] Peter Clote. Sequential, machine-independent characterizations of the parallel complexity classes ALOGT IME, AC^{k}, NC^{k} and NC. In Samuel R. Buss and P. Scott, editors, Proc. Workshop on Feasible Math., pages 49–69. Birkhäuser, 1989.

[8] Peter Clote. Polynomial size Frege proofs of certain combinatorial principles. In Peter Clote and Jan Krajíček, editors, Arithmetic, Proof Theory and Computational Complexity, pages 162–184. Oxford University Press, 1993.

[9] A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Logic, Methodology and Philosophy of Science II, pages 24–30. North-Holland, 1965.

[10] Kevin Compton and Claude LaFlamme. An algebra and a logic for NC^{1}. Information and Computation, 87:241–263, 1990.

[11] J. Lind. Computing in logarithmic space. Technical Report 52, Project MAC, Massachusetts Inst. of Technology, September 1974.

[12] W. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22:365– 383, 1981.