FUNCTION-ALGEBRAIC CHARACTERIZATIONS OF LOG AND

POLYLOG PARALLEL TIME

Stephen Bloch

Abstract. The main results of this paper are recursion-theoretic characterizations of two parallel complexity classes: the functions computable by uniform bounded fan-in circuit families of log and polylog depth (or equivalently, the functions bitwise computable by alternating Turing machines in log and polylog time). The present characterizations avoid the complex base functions, function constructors, and a priori size or depth bounds typical of previous work on these classes. This simplicity is achieved by extending the “tiered recursion” techniques of Leivant and Bellantoni & Cook. Key words. Circuit complexity; subrecursion. Subject classifications. 68Q15, 03D20, 94C99.

1. Introduction

Researchers in computational complexity have tried for decades to describe computational classes without reference to Turing machines or other specific models of computation. One early success, Cobham (1965), characterized the functions computable in polynomial time as the algebra generated from a few base functions by closure under composition and a form of recursion. Cobham’s characterization was substantially simplified with new techniques in Bellantoni & Cook (1992). By extending these techniques, I characterize two parallel function classes: the functions computable in parallel time proportional to the log, or to a polynomial in the log, of the input length. Here “parallel time” refers to either the alternating Turing machine or the uniform, bounded fan-in circuit family model of computation.

Cobham’s characterization inspired many other recursion-theoretic and logical characterizations of complexity classes. The Cobham characterization provided early support for FP as a natural class, but this support was weakened by the explicit bounds and unfamiliar base functions in the characterization. Such problems—artificial size or depth bounds, base functions introduced only for their growth rates, computationally complex base functions, and untidy collections of composition and recursion schemes—continued to plague later researchers. Lind (1974) gave a recursion-theoretic characterization of logspace, and Allen (1991) gave logical and recursion-theoretic characterizations of NC, both explicitly bounding function growth rates by polynomials. Compton & LaFlamme (1990) presented recursion-theoretic and logical characterizations of uniform NC^{1}, relying on a polynomial size bound implicit in their finite-models approach. Clote (1989) characterized uniform NC^{1}, AC^{0}, and a variety of other parallel classes with a polynomial-bounded recursion scheme, using a complete problem from Buss (1987). A more elegant characterization, in Clote (1993), used the completeness result of Barrington (1989) to simplify the base functions and impose a constant bound on recursively-defined functions. Buss (1986), using a variant of Cobham’s characterization, showed that the functions at each level of the polynomial-time hierarchy are precisely those provably total in a corresponding weak fragment of Peano arithmetic. Buss’s and Clote’s characterizations, however, required a language expressly designed to produce polynomial growth rates. Arai (1992) characterized uniform NC^{1} with systems of bounded arithmetic based on the “upward tree recursion” of Compton & LaFlamme (1990), while Clote & Takeuti (1992) did the same with a log-depth weak induction scheme; both of these used only the usual language of number theory but explicitly specified O(log(n)) recursion depth (and hence 2^{O(log(n))} = n^{O(1)} size).

By contrast, the results of this paper involve no explicit size or depth bounds, no functions introduced solely to produce desired growth rates, only computationally easy base functions—so easy as to be computable by constantdepth, bounded fan-in circuits—and only one composition and one recursion scheme. Essential to these simpler characterizations is the notion (introduced in Leivant 1990 and Bellantoni & Cook 1992) of classifying the parameters of a function into “tiers” by how they are used in the computation. The classification depends on whether a parameter is used only for local, bitwise operations or is used in its entirety to bound a loop or a recursion. The former sort of parameter has much less impact on the resources necessary to compute the function, and is called “safe,” or “tier 0;” the latter is called “normal,” or “tier 1.” (The “safe/normal” terminology is due to Bellantoni & Cook 1992. The “tier” terminology, due to Leivant 1990, generalizes to higher-numbered tiers. In this paper we shall only be concerned with tiers 0 and 1, so we use the two terminologies interchangeably.) By distinguishing tiers of parameters syntactically, one can bound computational resource costs without unduly limiting the system’s ability to perform simple operations. This technique allowed Bellantoni & Cook (1992) to characterize polynomial time with a function algebra that made no mention of polynomial growth rates.

The present paper applies the tiering technique for the first time to parallel complexity classes. I replace the scheme of recursion on notation used in Cobham (1965) and Bellantoni & Cook (1992) with a scheme of “divide and conquer recursion.” Divide and conquer recursion, without tiering, has been used under various names in Buss (1986), Compton & LaFlamme (1990), and Allen (1991), always with size and/or depth bounds artificially imposed somehow. With tier discipline, however, the desired size and depth bounds follow naturally from the recursion scheme itself.

The main results of this paper are summed up in the following two theorems, whose terminology will be defined later:

Theorem 1. For functions f : ({0, 1}^{∗})^{k} ↦ {0, 1}^{∗}, the following are equivalent:

1. f(x⃗; ) ∈ vsc(BASE) with a length mask;

2. f is bitwise computable in alternating log time;

3. f is computable with a length mask by a U_{E^{∗}}-uniform family of multioutput NC^{1} circuits.

Theorem 2. For functions f : ({0, 1}^{∗})^{k} ↦ {0, 1}^{∗}, the following are equivalent:

1. f(x⃗; ) ∈ sc(BASE) with a length mask;

2. f is bitwise computable in alternating polylog time;

3. f is computable with a length mask by a U_{E^{∗}}-uniform family of multioutput, bounded fan-in, polylog depth circuits;

4. f is computable in deterministic polylog space, not counting a write-only output tape.

The “length masks” in these theorems address the sticky question of computing the precise length of a function value. The following special cases, in which function lengths are smooth (e.g., not merely bounded by but equal to a polynomial), are easier to use and suffice for most practical purposes.

Corollary 3. If there is a polynomial p with nonnegative integer coefficients such that for all x⃗, |f(x⃗; )| = p(|x⃗|), then the following are equivalent:

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

2. f is bitwise computable in alternating log time;

3. f is computable by a U_{E^{∗}}-uniform, multi-output, NC^{1} circuit family.

Corollary 4. If there is a polynomial p with nonnegative integer coefficients such that for all x⃗, |f(x⃗; )| = 2^{p(||x⃗||)}, then the following are equivalent:

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

2. f is bitwise computable in alternating polylog time;

3. f is computable by a U_{E^{∗}}-uniform, multi-output, bounded fan-in, polylog depth circuit family;

4. f is computable in deterministic polylog space, not counting a write-only output tape.

2. Outline

In Section 3, I define three operations on functions: “safe composition,” “safe divide-and-conquer recursion,” and “very safe divide-and-conquer recursion;” the last two differ only in the strictness of their tier discipline. I then define a small collection of computationally easy BASE functions. Closing these BASE functions under safe composition and safe divide-and-conquer recursion yields a function algebra sc(BASE); closing under safe composition and very safe divide-and-conquer recursion yields a smaller algebra vsc(BASE).

The rather technical Section 4 discusses circuit families and uniformity conditions. While the main theorems characterize log-depth and polylog-depth circuit computation, both of which are well understood, the less common notion of constant-depth (NC^{0}) circuits seems essential to the proofs. I define this notion, along with suitable uniformity conditions, in this section.

In Section 5, I prove that functions in vsc(BASE) have polynomial growth, and those in sc(BASE) have 2^{polylog} growth. I then show that functions in vsc(BASE) are computable in uniform log depth, and those in sc(BASE) are computable in uniform polylog depth. This proves implications (1 ⇒ 3) of Theorems 1 and 2. Equivalences (3 ⇔ 2) of both theorems follow from Ruzzo (1981), while (2 ⇔ 4) of Theorem 2 follows from Chandra et al. (1981).

In Section 6, I prove the implications (2 ⇒ 1) of both main theorems. This is done by arithmetizing the computation of an alternating Turing machine and showing both that vsc(BASE) can correctly generate and evaluate the computation tree of a log-time alternating machine, and that sc(BASE) can generate and evaluate the computation tree of a polylog-time alternating machine. Thus any function whose bit-graph is in log (respectively polylog) alternating time is bitwise computable by a function in vsc(BASE) (respectively sc(BASE)). By a comprehension lemma, such bitwise computability extends to computability of the whole function within vsc(BASE) (respectively sc(BASE)) so long as the function’s growth rate is sufficiently slow and easily computed. Corollaries 3 and 4 follow because the alternating and space-bounded machines cannot compute more than (quasi)polynomially long function values: if they did, by a simple pumping lemma, they would compute infinitely long values.

Finally, Section 7 compares these results with others in the field and discusses possible extensions of the technique.

3. Definitions

3.1. Notation. Most functions discussed in this paper operate on bit strings, finite strings over {0, 1}. The length of a string x ∈ {0, 1}^{∗} is written |x|. The symbol λ stands for the empty string. If x⃗ is a tuple x_{1}, …, x_{k}, the notation |x⃗| means the tuple |x_{1}|, …, |x_{k}|. The notation a−^{.}b, where a and b are natural numbers (e.g., lengths of strings), means max(a − b, 0). The notation Bit(i, y) denotes the bit i places from the right end of the bit-string y, or 0 if i > |y|, treating the bit-string i as a binary representation of a number. Similarly, when we speak of a machine or a circuit computing on natural numbers, we mean binary representations of those numbers unless stated otherwise.

The functions discussed in this paper are tiered functions, functions that distinguish between normal and safe formal parameters. Following Leivant (1990) and Bellantoni & Cook (1992), we write the normal parameters first, separated from the safe parameters with a semicolon. For example, in the function f(x, z; b, y), x and z are normal, b and y safe. A function f(x_{1}, …, x_{j}; y_{1}, …, y_{k}) represents a map from ({0, 1}^{∗})^{j+k} to {0, 1}^{∗}. A function name is upper-case if the function is defined within the systems sc(BASE) or vsc(BASE) from simpler functions; primitive functions have mixed-case names.

A function has polynomial growth if its length is bounded by a polynomial p(|x⃗|) in the lengths of its inputs. A function has quasipolynomial growth (see Barrington 1992) if its length is bounded by a function of the form 2^{p(||x⃗||)}, for polynomial p, or equivalently if the length of its length is bounded by a polynomial p(||x⃗||) in the lengths of the lengths of its inputs.

3.2. The Function Algebras.

Definition 5. The set BASE comprises constants λ, 0, 1, projection functions π_{k}^{i,j}(x_{1}, …, x_{i}; x_{i+1}, …, x_{i+j}) = x_{k}, and the following functions:

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’s rightmost bit is 1 \\ Lsp(; v, max(u, v)) & if b’s rightmost bit is 0, or b = λ \end{cases}
Conc(; x, y) = the concatenation of x and y
Bh(; x) = the rightmost ⌈|x|/2⌉ bits of x (“back half”)
Fh(; 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, first left-extending the

shorter with zeroes to the same length as the longer

And(; x, y) = the bitwise AND of x and y, similarly
Ins_{0}(; x) = x with a 0 inserted after each bit, e.g.,

Ins_{0}(; 01101) = 0010100010

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

Definition 6. (Bellantoni & Cook) We say a 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 the safe parameters y⃗ to f cannot be used as normal, nor can they in any way affect a value which is used as a normal parameter to g. On the other hand, the normal parameters x⃗ to f can affect the values of the v’s, which g treats as safe.

Allen (1991) introduced a scheme of “branching recursion.” I prefer the more descriptive name “divide and conquer recursion,” or DCR for short. By adding tier discipline to this scheme we get the following definition.

Definition 7. Function f(z, b, x⃗; y⃗) is defined by safe divide-and-conquer recursion (henceforth safe DCR) from 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(z, x⃗; y⃗, f(Fh(; z), b, x⃗; y⃗), f(Bh(; z), b, x⃗; y⃗)) & if |z| > max(|b|, 1) \end{cases}

Definition 8. Function f(z, b, x⃗; y⃗) is defined by very safe divide-and-conquer recursion (henceforth very safe DCR) from 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(; z, x⃗, y⃗, f(Fh(; z), b, x⃗; y⃗), f(Bh(; z), b, x⃗; y⃗)) & if |z| > max(|b|, 1) \end{cases}

Note that safe and very safe DCR differ only in the tiers of the parameters to the iterated function h: in very safe DCR the iterated function takes no normal parameters at all, and therefore cannot itself be defined by recursion (since both recursion schemes require at least one normal parameter z).

Definition 9. The safe closure of BASE, or sc(BASE), is the set of functions definable from BASE functions by finitely many applications of safe composition and safe DCR.

Definition 10. The very safe closure of BASE, or vsc(BASE), is the set of functions definable from BASE functions by finitely many applications of safe composition and very safe DCR.

3.3. Simultaneous Recursion. Many recursion schemes explicitly allow defining a tuple of functions simultaneously based on a tuple of their previous values.

Definition 11. The functions f_{1}(z, b, x⃗; y⃗), …, f_{k}(z, b, x⃗; y⃗) are defined by simultaneous, safe divide-and-conquer recursion from the functions g_{1}, …, g_{k} and h_{1}, …, h_{k} if, for all 1 ≤ i ≤ k,

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

Simultaneous, very safe divide-and-conquer recursion is defined analogously. Simultaneous (very) safe DCR is in fact no more powerful than ordinary

(very) safe DCR, in the presence of a recursion-free way to encode and decode k-tuples. With encoding and decoding, we can define a single function H which extracts elements of a tuple, applies the appropriate h functions, and combines the results back into a tuple; (very) safe DCR on this H function produces a function

F (z, b, x⃗; y⃗) = ⟨f_{1}(z, b, x⃗; y⃗), …, f_{k}(z, b, x⃗; y⃗)⟩,

from which one can extract any of the functions f_{i}.

Such encoding and decoding seem difficult in vsc(BASE) and sc(BASE). But they are easy in the restricted case that all the elements of the tuple are the same length, and this restricted case suffices for our purposes. We define a family of encoding and decoding functions as follows.

COMB_{1}(; x)  = x
COMB_{2i}(; x_{1}, …, x_{2i})  =
Conc(; COMB_{i}(; x_{1}, …, x_{i}), COMB_{i}(; x_{i+1}, …, x_{2i})) for i > 0
COMB_{2i−1}(; x_{1}, …, x_{2i−1}) =

Conc(; COMB_{i}(; x_{1}, …, x_{i}), COMB_{i}(; x_{i+1}, …, x_{2i−1}, x_{2i−1})) for i > 1

EXTR_{1}^{1}(; y)  = y
EXTR_{k}^{i}(; y)  = \{ \begin{matrix}EXTR_{⌈k/2⌉}^{i}(; Fh(y)) & if i ≤ ⌈k/2⌉ \\ EXTR_{⌈k/2⌉}^{i−⌈k/2⌉}(; Bh(y)) & if ⌈k/2⌉ < i ≤ k \end{matrix}

We leave the reader to verify that for all tuples a⃗ such that |a_{1}| = ⋯ = |a_{k}| and for all 1 ≤ i ≤ k, we have EXTR_{k}^{i}(; COMB_{k}(; a_{1}, …, a_{k})) = a_{i}.

Lemma 12. If f_{1}, …, f_{k} are defined by simultaneous, very safe DCR from functions in vsc(BASE), and if, for all z, b, x⃗, y⃗, |f_{1}(z, b, x⃗; y⃗)| = ⋯ = |f_{k}(z, b, x⃗; y⃗)|, then f_{1}, …, f_{k} ∈ vsc(BASE).

The proof of this lemma is straightforward, relying on the COMB and EXTR functions taking no normal parameters. With this lemma in hand (and the analogous result with “very safe” replaced by “safe” and vsc(BASE) replaced by sc(BASE)), we may use simultaneous DCR freely whenever all the functions f_{1}, …, f_{k} are guaranteed to have the same length.

3.4. Alternating Turing machines. Many of the results herein involve computation by alternating Turing machines, or ATM’s, defined in Chandra et al. (1981). I omit the complete definition, but point out the conventions particular to our setting. Our machines will have l read-only input tapes, k work tapes, and no output tape (they “output” only an accept/reject decision).

Definition 13. An ATM configuration is a tuple ⟨q, L_{1}, …, L_{k}, R_{1}, …, R_{k}⟩ where

∘ q is the current state, and

∘ L_{1}, …, L_{k}, R_{1}, …, R_{k} ∈ {0, 1}^{∗} represent the contents to the left and right of the head on each of k work tapes.

The symbol under head i is bit 0 of L_{i}, the symbol to the left is bit 1 of L_{i}, and so on. The symbol to the right of head i is bit 0 of R_{i}, the symbol to the right of that is bit 1 of R_{i}, and so on (i.e., the R’s are stored reversed).

Note that the input tapes are not an explicit part of a configuration.

We make certain additional assumptions about our ATM’s.

∘ Each ATM has a time bound t, a function of its input lengths, such that the result of the computation tree on input X⃗ is determined by the first t(|X⃗|) time steps.

∘ For all input lengths, t is at least the log of the number of states.

∘ Each R_{i} and each L_{i} is initially a t-bit string of zeroes.

∘ Access to the input tape occurs only at the leaves of the computation tree, at “input configurations.” Each input configuration is characterized by three numbers 1 ≤ i ≤ k, 1 ≤ j ≤ l, and b ∈ {0, 1}, which are encoded in the state. The input configuration accepts iff the symbol b appears on input tape j in the position whose binary representation is L_{i}.

∘ Each non-input configuration has exactly two successor configurations.

∘ The non-input configurations on each path alternate strictly between universal and existential configurations, starting with an existential.

These assumptions increase the running time of the ATM by only a constant factor, as one can see by standard techniques.

The class of relations decidable by an ATM in O(log(max input length)) time is called ALOGTIME; the class decidable in log^{O(1)}(max input length) time is called APLOGTIME.

ATM’s as defined above technically compute only relations, not functions. However, it is common in the literature to construct ATM’s that compute the bit-graph of a function, and by a slight abuse of terminology say that the ATM computes the corresponding function.

Definition 14. The function f(x⃗) : ({0, 1}^{∗})^{k} ↦ {0, 1}^{∗} is bitwise computable in ALOGTIME (resp. APLOGTIME) iff both of the following languages are recognizable in ALOGTIME (resp. APLOGTIME):

∘ {⟨x⃗, i⟩ : i < |f(x⃗)|}

∘ {⟨x⃗, i, b⟩ : Bit(i, f(x⃗)) = b}

3.5. Function Length. All the BASE functions have the property that the length of the output is a function of the lengths of the inputs. This is necessary for our model of circuit computation to make sense. However, one may reasonably want to compute functions from ({0, 1}^{∗})^{k} to {0, 1}^{∗} without this property. For such applications we introduce the notion of length masks.

Definition 15. Given a function class C, the function f(x⃗; y⃗) is in C with a length mask if there are two functions B_{f}(x⃗; y⃗) (the bits of f) and L_{f}(x⃗; y⃗) (the length mask of f), both in C, such that

∘ For all x⃗, y⃗, we have L_{f}(x⃗; y⃗) ∈ 0^{∗}1^{∗}, and

∘ For all x⃗, y⃗, the value of f(x⃗; y⃗) is the value of B_{f}(x⃗; y⃗) restricted to the bit positions in which L_{f}(x⃗; y⃗) has a 1.

For example, if C is the class of functions f(x⃗) such that Bit(i, f(x⃗)) is an ALOGTIME or APLOGTIME relation of i and x⃗, this definition reduces to Definition 14. It differs mainly in being based on a function class, rather than a relation class.

4. Circuits and Uniformity

In this section we define a model of circuit computation and discuss the uniformity conditions necessary to prove the main theorems.

4.1. NC^{0} circuits. The smallest complexity class generally studied in circuit complexity is AC^{0}, the class of relations computable by circuit families of constant depth, using polynomial-fan-in AND and OR gates. If the gates are restricted to constant fan-in, the resulting class is called NC^{0}. When considered as a relation class, NC^{0} is trivial because the single bit of output can only depend on constantly many bits of input. But in a multi-output circuit model, NC^{0} circuits can compute many useful functions, including all the BASE functions.

Definition 16. A function f(x_{1}, …, x_{j}; y_{1}, …, y_{k}) is in F NC^{0} if it is computed by a constant depth, linear size, multiple output, bounded fan-in circuit family.

(For convenience, suppose the gate set includes the constants 0 and 1, the singleinput identity and NOT functions, and two-input AND, OR, left and right projections. Any complete basis would suffice, at the cost of longer proofs).

Fact 17. All the BASE functions are in F NC^{0}.

We prove this Fact, and elaborate on it, in Lemma 24.

4.2. Uniformity. As usual in circuit complexity theory, uniformity becomes a more crucial and delicate consideration as the circuits themselves become weaker. The most widely accepted notion of uniformity for log- and higherdepth circuits is the following, introduced in Ruzzo (1981):

Definition 18. (Ruzzo) The extended connection language of a circuit family of size Z(n) is the set of 4-tuples ⟨n, γ, p, τ⟩ such that n is the binary representation of the number of inputs to the circuit, γ is a binary number identifying a gate in the circuit, p ∈ {L, R}^{∗}, and either p = ϵ and τ is the type of gate γ in some fixed encoding (the type of an internal gate is the Boolean function it computes, while the type of an input gate is a binary number indicating which bit of input it is), or p represents a nontrivial path of at most log(Z(n)) left/right decisions and τ is a binary number identifying the descendant of γ reached by following that path.

Definition 19. (Ruzzo) A family of bounded fan-in circuits of size Z(n) and depth t(n) is U_{E^{∗}}-uniform if its extended connection language is recognizable by an ATM in time O(t(n)) and space O(log(Z(n))).

Unfortunately, this definition makes no sense for constant-depth circuits, as constant time is insufficient even to examine a gate number or an input length. So we separate the uniformity computation into two phases, one taking constant time based on partial information about a gate, and a second combining the first phase with the rest of the information about the circuit. Composing or iterating functions will correspond to composing or iterating the first phase; the second phase is only applied once, and its greater cost amortized.

Before describing these phases, though, we adopt a simple system of numbering the gates in a circuit. First, all circuits henceforth will be treelike, so that each gate γ descends by a unique path σ_{γ} ∈ {L, R}^{∗} from a unique output gate OUT_{γ}. The output bit position OUT_{γ} and the path σ_{γ} jointly determine γ. We accordingly identify the “gate number” γ in Ruzzo’s definition with the pair (OUT_{γ}, σ_{γ}).

Under this gate numbering scheme, determining the gate descended from γ along a path p is easy (simply concatenate p to σ_{γ}, in deterministic time O(|p|+|σ_{γ}|)). Determining the type of an internal gate is also reasonably easy; I come back to this later. The difficult part, which calls for the two-phase approach, is determining which input bit is tied to a given input gate.

In the first phase, a (deterministic, multi-tape) Turing machine translates a path σ into an open term t_{σ}(x), taking time proportional to |σ|, which is bounded by circuit depth. The term is constructed from the following language, which may be thought of as mapping an output bit position to an input bit position that “affects” it (i.e., there are two inputs, differing only in the specified bit position, that produce different output). In addition to the natural numbers that indicate bit positions, we use a symbol ⊥ to indicate that no input bit affects the given output bit.

For a circuit with k inputs y_{1}, …, y_{k} ∈ {0, 1}^{∗}, the mapping language contains the following 3k + 3 function symbols (the reasons for this choice will become clear in Lemma 24):

Undef(x) = ⊥, regardless of x
Zero(x) = \{ \begin{matrix}⊥ & if x =⊥ \\ 0 & otherwise \end{matrix}
Halve(x) = \{ \begin{matrix}⊥ & if x =⊥ \\ ⌊\frac{x}{2}⌋ & otherwise \end{matrix}
Add_{j}(x) = \{ \begin{matrix}⊥ & if x =⊥ \\ x + |y_{j}| & otherwise, for 1 ≤ j ≤ k \end{matrix}
Sub_{j}(x) = \{ \begin{matrix}⊥ & if x =⊥ \\ x −^{.} |y_{j}| & otherwise, for 1 ≤ j ≤ k \end{matrix}
AddHalf_{j}(x) = \{ \begin{matrix}⊥ & if x =⊥ \\ x + ⌈\frac{|y_{j}|}{2}⌉ & otherwise, for 1 ≤ j ≤ k \end{matrix}

In the second phase, an ATM evaluates this term by plugging in the lengths |y⃗| and substituting OUT_{γ} for x, taking time O(log(max(|t_{σ}|, |y_{j}|, OUT_{γ}))).

We are now ready to formally define our uniformity criterion.

Definition 20. A circuit family is mapping-uniform if there is a deterministic, multi-tape Turing machine P and an ATM Q such that for any gate (OUT_{γ}, σ_{γ}) in a circuit of the family,

∘ if (OUT_{γ}, σ_{γ}) is an input gate tied to bit r of some parameter, then machine P on input σ_{γ} runs in time O(|σ_{γ}|) and outputs a term t_{σ_{γ}} in the mapping language such that t_{σ_{γ}}(OUT_{γ}) = r, and

∘ machine Q on input OUT_{γ}, σ_{γ}, |y_{1}|, …, |y_{k}|, τ runs in alternating time O(log(max(OUT_{γ}, |σ_{γ}|, |y_{1}|, …, |y_{k}|))) and accepts iff either (OUT_{γ}, σ_{γ}) is an internal gate with type τ, or (OUT_{γ}, σ_{γ}) is an input gate tied to bit r of y_{j} and τ = ⟨j, r⟩ (in some standard encoding).

Lemma 21. Any mapping-uniform circuit family of O(log) or polylog depth is also U_{E^{∗}}-uniform.

Proof. Straightforward. □

Lemma 22. If f is defined by safe composition from g, u⃗, and v⃗, all of which have mapping-uniform circuit families, then f has a mapping-uniform circuit family of depth at most proportional to the maximum depth of the families for g, u⃗, and v⃗.

Proof. Suppose, for simplicity, that there are only one u and one v function, so f(x⃗; y⃗) = g(u(x⃗; ); v(x⃗; y⃗)). The natural circuit to compute f would be a g circuit with its inputs tied to the outputs of u and v circuits. Unfortunately, machine P would have insufficient time to decide whether a given path went into a u or a v circuit. So we attach each input of g to the output of a projection gate whose left input comes from a u circuit and whose right input comes from a v circuit. Now machine P can tell from σ_{γ} alone whether gate γ is in a g, a u, or a v subcircuit. Machine Q bears responsibility for deciding whether the projection gate is a left or a right projection.

Any path σ through the resulting circuit for f can be written as an initial portion σ^{g} passing through the g subcircuit, an additional branch through the projection gate, and a remaining portion σ^{u} or σ^{v}, depending on which path was taken through the projection gate. The term t_{σ} is simply the composition of t_{σ^{g}} and either t_{σ^{u}} or t_{σ^{v}}; if the terms for all the subcircuits could be produced in linear time (in the lengths of paths), so can the term for the f circuit.

Determining the descendant of a given gate along a given path p, as before, is easy: concatenate p to the path portion of the gate number. To determine the type of a gate in the g subcircuit, simply invoke the uniformity of g. To determine the type of a gate anywhere else in the circuit, note that each such gate descends from a unique input gate to g, so we can use the uniformity of g on σ^{g} to decide which input it is. This tells us whether the gate is in a u or a v subcircuit, and from which output of the u or v subcircuit our gate descends. Then by the uniformity of u and v we can determine the type of gate γ. □

4.3. Properties of the Mapping Language. The mapping language defined in Section 4.2 has two important properties: terms in it can be efficiently evaluated, and it encapsulates all the possible input-output dependencies for functions in our algebras.

Lemma 23. Let m = max(OUT_{γ}, |y_{1}|, …, |y_{k}|). There is an ATM which recognizes the set

{⟨|y_{1}|, …, |y_{k}|, OUT_{γ}, t_{σ_{γ}}, r⟩ : r = t_{σ_{γ}}(OUT_{γ})}

in time O(log(max(|t_{σ_{γ}}|, m))).

For all the uses we shall make of this lemma, time O(max(|t_{σ_{γ}}|, m)) would suffice. This gap suggests we could get rid of the alternation, but I have found no deterministic algorithm taking time less than θ(max(|t_{σ_{γ}}|, m)^{2}). Proof. Suppose the term t_{σ_{γ}} does not contain the symbols Undef, Zero, or Halve. Evaluating t_{σ_{γ}}(OUT_{γ}) simply requires adding and subtracting a list of binary numbers from among OUT_{γ}, |y_{1}|, …, |y_{k}|, and ⌈|y_{1}|/2⌉, …, ⌈|y_{k}|/2⌉. Each symbol in the term corresponds directly to one element of this list, so the list can be bitwise constructed in ALOGTIME. Each of these numbers is at most log(m) bits long, and there are at most |t_{σ_{γ}}| of them, so they can be added (and subtracted, using two’s-complement representation) by the carrysave addition algorithm in time O(log(max(m, |t_{σ_{γ}}|)).

Now allow Halve symbols, but no Undef or Zero symbols, in the term. Each non-Halve symbol in the term corresponds to an element of the list. For each such symbol in parallel, count how many Halve symbols appear after it in the term and multiply the corresponding element of the list by two to that power. Add up the list as before, then divide the result by two to the power of the total number of HALV E symbols in the list, rounding down. All this multiplication and division is implemented by bit-shifts, i.e., addition and subtraction of bit positions, which takes O(log(m)) alternating time.

To evaluate an arbitrary term in the language, guess where an Undef symbol appears and confirm it. If so, the answer is ⊥. If not, for each entry in the list, guess and confirm the position of a Zero before it, and if there is one, replace the entry with 0 before applying the above algorithm. □

For example, evaluating the term

Add_{2}(Halve(Sub_{3}(Halve(AddHalf_{4}(OUT_{γ})))))

corresponds to adding up the list (4|y_{2}|, −2|y_{3}|, ⌈\frac{|y_{4}|}{2}⌉ , OUT_{γ}) and dividing by four, while evaluating the term

Halve(Add_{1}(AddHalf_{2}(Halve(Zero(Add_{3}(OUT_{γ}))))))

corresponds to adding up the list (2|y_{1}|, 2 ⌈\frac{|y_{2}|}{2}⌉ , 0, 0) and dividing by four.

Lemma 24. All the BASE functions have mapping-uniform F NC^{0} circuits.

Proof.

∘ For the projection functions π_{k}^{i,j}, term t_{σ_{γ}}(x) is just x (that is, output bit OUT_{γ} depends only on bit OUT_{γ} of some parameter). Let machine Q accept iff σ_{γ} is empty, τ = ⟨k, OUT_{γ}⟩, and OUT_{γ} < |y_{k}|.

∘ For the constant functions λ, 0, and 1, t_{σ_{γ}}(x) is UNDEF (x), since these functions do not depend on input. For λ there are no gates whatsoever, so let machine Q reject unconditionally; for 0 and 1 we let machine Q accept iff τ indicates the appropriate constant-valued gate (and σ_{γ} is empty).

∘ For the Msp(; y_{1}, y_{2}) function, output bit OUT_{γ} is Bit(OUT_{γ} + |y_{2}|, y_{1}), so t_{σ_{γ}}(x) is ADD_{2}(x). Let machine Q accept iff OUT_{γ} + |y_{2}| < |y_{1}| and τ indicates the appropriate input bit.

∘ For the Lsp(; y_{1}, y_{2}) function, output bit OUT_{γ} is Bit(OUT_{γ}, y_{1}), so t_{σ_{γ}}(x) is just x. Machine Q accepts iff OUT_{γ} < |y_{2}| and τ indicates the appropriate input bit.

∘ Bit OUT_{γ} of Cond(; y_{1}, y_{2}, y_{3}) is

(Bit(0, y_{1})) ∧ Bit(OUT_{γ}, y_{2})) ∨ (¬Bit(0, y_{1}) ∧ Bit(OUT_{γ}, y_{3})),

which can be evaluated naturally by a circuit of depth 3. So t_{σ_{γ}}(x) is either x or ZERO(x), depending on which of the constantly many possibilities σ_{γ} is. Machine Q also tests these constantly many possibilities, as well as whether |y_{1}| = 0, OUT_{γ} < |y_{2}|, and OUT_{γ} < |y_{3}|, and recognizes the appropriate τ.

∘ For the Conc(; y1, y2) function, bit OUT_{γ} is either Bit(OUT_{γ}, y_{2}) or Bit(OUT_{γ} − |y_{2}|, y_{1}), whichever one exists. Unfortunately, machine P has no access to OUT_{γ} or |y_{2}|, so we insert a two-input projection gate with left input Bit(OUT_{γ}, y_{2}) and right input Bit(OUT_{γ} − |y_{2}|, y_{1}), as in the proof of Lemma 22. Machine P can tell from σ_{γ} whether to output the term x or the term SUB_{2}(x). Machine Q bears responsibility for testing whether OUT_{γ} < |y_{2}| and choosing a left or a right projection gate accordingly. Note that if x < |y_{j}|, it will choose a left projection and the resulting circuit will pay no attention to Bit(Sub_{2}(OUT_{γ}), y_{1}), so it makes no difference what bit it is.

∘ Bit OUT_{γ} of Bh(; y_{1}) is Bit(OUT_{γ}, y_{1}), so P outputs x. Machine Q accepts iff OUT_{γ} < ⌈|y_{1}|/2⌉ and τ indicates the appropriate input bit.

∘ Bit OUT_{γ} of Fh(; y_{1}) is Bit(OUT_{γ} + ⌈|y_{1}|/2⌉, y_{1}), so P outputs the term ADDHALF (x). Machine Q tests whether the relevant bit actually exists.

∘ The Not(; y_{1}) function is computed by a single layer of NOT gates. Machine P outputs x, since bit OUT_{γ} of output depends on bit OUT_{γ} of input. Machine Q is straightforward.

∘ The Or(; y_{1}, y_{2}) function is computed by a layer of two-input OR gates, whose inputs are tied either to input gates of the circuit or to constant-0 gates. Again P outputs simply x. Machine Q must check whether OUT_{γ} < |y_{1}| and OUT_{γ} < |y_{2}| in addition to its usual duties.

∘ The Ins_{0}(; y_{1}) function involves only input and constant-valued gates, but bit OUT_{γ} of output may depend on bit ⌊OUT_{γ}/2⌋ of y_{1}, so machine P outputs HALV E(x). Machine Q must check whether OUT_{γ} is even or odd, and decide whether the gate is a constant 0 or an input gate, in addition to its usual duties. □

Corollary 25. Any function in vsc(BASE) or sc(BASE) which has no normal parameters is in mapping-uniform F NC^{0}.

Proof. Any function with no normal parameters must be defined solely by safe composition from BASE functions. Safe composition preserves both linear growth rate and (by Lemma 22) mapping-uniform constant depth, so any such function has linear-size, constant-depth, mapping-uniform circuits. □

5. Bounding sc(BASE) and vsc(BASE)

In this section, we prove upper bounds on both the growth rate and the necessary circuit depth of functions in vsc(BASE) and sc(BASE).

5.1. Function growth.

Lemma 26. 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(1, |y⃗|).

Proof. By induction on the vsc(BASE) definition of f.

If f has no normal parameters x⃗, then it has linear growth rate by Corollary 25, so we can simply let p_{f} be the multiplicative constant. If f is a BASE function, then either it is a projection function (with linear growth) or it has no normal parameters.

If f is defined by safe composition, e.g., f(x⃗; y⃗) = g(u(x⃗; ); v(x⃗; y⃗)), then let p_{g}, p_{u}, and p_{v} satisfy the inductive hypothesis.

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

which has the desired form. The argument for multiple functions u⃗ and v⃗ is similar.

If f is defined by very safe DCR, e.g.,

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

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

then let polynomial p_{g} and constant p_{h} satisfy the inductive hypothesis.

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

≤ max(\begin{matrix}|g(b, x⃗; y⃗)|, \\ p_{h} · max(1, |z|, |x⃗|, |y⃗|, |f(Fh(; z), b, x⃗; y⃗)|, |f(Bh(; z), b, x⃗; y⃗)|)) \end{matrix}
≤ max(|g(b, x⃗; y⃗)|, p_{h}^{log(|z|)} · max(|x⃗|, |y⃗|, |g(b, x⃗; y⃗)|))

by a straightforward induction on ||z||

≤ p_{h}^{log(|z|)} · max(1, |x⃗|, |y⃗|, |g(b, x⃗; y⃗)|))
≤ |z|^{log(p_{h})} · max(1, |x⃗|, |y⃗|, |g(b, x⃗; y⃗)|))
≤ |z|^{log(p_{h})} · max(1, |x⃗|, |y⃗|, p_{g}(|b|, |x⃗|) · max(1, |y⃗|))
≤ |z|^{log(p_{h})} · (∑ |x⃗|) · p_{g}(|b|, |x⃗|) · max(1, |y⃗|)),

which has the desired form. □

Lemma 27. 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(1, |y⃗|).

Proof. The base and composition cases are similar to those in the previous lemma.

If f is defined by safe DCR, e.g.,

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

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

then let p_{g} and p_{h} satisfy the inductive hypothesis.

|f(z, b, x⃗; y⃗)| ≤ max(\begin{matrix}|g(b, x⃗; y⃗)|, \\ 2^{p_{h}(||z||,||b||,||x⃗||)} · max(\begin{matrix}1, |y⃗|, |f(Fh(; z), b, x⃗; y⃗)|, \\ |f(Bh(; z), b, x⃗; y⃗)|)) \end{matrix} \end{matrix}

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

which has the desired form. □

5.2. Circuit depth.

Lemma 28. If f(x⃗; y⃗) ∈ vsc(BASE), then f has mapping-uniform circuits of depth O(log(|x⃗|)), independent of |y⃗|.

Proof. If f ∈ BASE, then it is in mapping-uniform F NC^{0} by Lemma 24.

If f is defined by safe composition, e.g., f(x⃗; y⃗) = g(u(x⃗; ); v(x⃗; y⃗)), then by Lemma 22, f has mapping-uniform circuits of depth

O(max((depth of g), (depth of u), (depth of v))).

We know by the induction hypothesis that the depths of u and v circuits are O(log(|x⃗|)), and the depth of g circuits is O(log(|u(x⃗; )|)). By Lemma 26, |u(x⃗; )| is polynomial in |x⃗|, so O(log(|u(x⃗; )|)) is simply O(log(|x⃗|)). It follows that the depth of the whole f circuit is O(log(|x⃗|)).

If f is defined by very safe DCR, e.g.,

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

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

then let G and H be circuit families satisfying the inductive hypothesis for g and h respectively. A natural circuit for f consists of a binary tree of height log(|z|) of (constant-depth) H circuits, with a layer of G circuits at the bottom. This clearly has logarithmic depth, since H has constant depth and G logarithmic depth; it remains only to prove it mapping-uniform.

As in the proof of Lemma 22, we glue the layers of the binary tree and the layer of G circuits together with projection gates, so the P machine can construct the mapping term t_{σ} from σ without knowing which input comes from which parameter. The P machine divides the path σ into subpaths passing through single H circuits, separated one from another by the branch through the projection gate, possibly followed by a sub-path through a G subcircuit. The term t_{σ} is simply the composition of the terms corresponding to these various subpaths, and since they can each be constructed in linear time (in |σ|), so can t_{σ}.

The Q machine may get one of two kinds of queries about the circuit. One type of query, finding the descendant gate of a given gate along a given path, is as usual trivial because of our gate-numbering scheme. The other type requires finding the type of a gate γ. In this case, Q will first measure the length of the path σ_{γ} and, by comparing it with the depth of H and with log(|z|), divide σ_{γ} into two parts: σ^{previous} passing from the root, possibly through many layers of H subcircuits, to the output of the G or H subcircuit containing γ, and σ^{local} passing from the output of the local subcircuit down to γ. The Q machine evaluates the term t_{σprevious} by Lemma 23 to determine which output of the local subcircuit γ descends from. It can then apply the uniformity of the local subcircuit with σ^{local} to determine the type of gate γ.

Thus, the circuits constructed to evaluate functions defined by very safe DCR are mapping-uniform, and the lemma follows by induction. □

Corollary 29. Any function in vsc(BASE) is computable by multi-output, U_{E^{∗}}-uniform NC^{1} circuits.

The implication (1 ⇒ 3) of Theorem 1 follows immediately.

Lemma 30. If f(x⃗; y⃗) ∈ sc(BASE), then there is a polynomial q_{f} such that f has mapping-uniform circuits of depth at most q_{f}(||x⃗||) · max(1, ||y⃗||).

Proof. The base case is similar to that in the previous lemma.

If f is defined by safe composition, e.g., f(x⃗; y⃗) = g(u(x⃗; ); v(x⃗; y⃗)), then by Lemma 22, f has mapping-uniform circuits of depth

O(max((depth of g), (depth of u), (depth of v))).

We know, by the induction hypothesis, that the depths of u and v circuits are polylog in |x⃗| and O(log) in |y⃗|, while the depth of g circuits is at most q_{g}(||u(x⃗; )||)·max(1, ||v(x⃗; y⃗)||). By Lemma 27, |u(x⃗; )| ≤ 2^{p_{u}(||x⃗||)} and |v(x⃗; y⃗)| ≤ 2^{p_{v}(||x⃗||)} · max(1, |y⃗|) for some polynomials p_{u} and p_{v}, so the depth of g circuits is at most q_{g}(p_{u}(||x⃗||)) · max(1, p_{v}(||x⃗||) + max(1, ||y⃗||)), which is at most q_{g}(p_{u}(||x⃗||)) · (p_{v}(||x⃗||) + 1) · max(1, ||y⃗||)), which has the desired form.

If f is defined by safe DCR, e.g.,

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

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

then let G and H be circuit families satisfying the inductive hypothesis with polynomials q_{g} and q_{h} respectively. The natural circuit family F to compute f is again a binary tree of H circuits, with a layer of G circuits at the bottom. By the induction hypothesis, the depth of each G and H subcircuit is polylog in the lengths of its normal parameters and O(log) in the lengths of its safe parameters. The depth of the F circuits is therefore O(log(|z|)) times the depth of H circuits plus the depth of G circuits, which (since z is normal) is likewise polylog in the lengths of the normal parameters and O(log) in the lengths of the safe parameters. The mapping-uniformity of F is proven as in the previous lemma. □

Corollary 31. Any function in sc(BASE) is computable by multi-output, U_{E^{∗}}-uniform, polylog depth, bounded fan-in circuits.

The implication (1 ⇒ 3) of Theorem 2 follows immediately.

6. Simulating Circuits

It remains to show that functions bitwise computable in ALOGTIME are in vsc(BASE) with a length mask, and that functions bitwise computable in APLOGTIME are in sc(BASE) with a length mask.

6.1. Bootstrapping. We start by defining a number of utility functions in vsc(BASE) and sc(BASE). We shall use definition by cases freely, so long as the choice of cases is decidable without recursion; any such definition expands straightforwardly into a few applications of Cond.

The function ZEROES(; x) = Lsp(; λ, x) returns a string of zeroes of the same length as x.

The function TWIN(; x) = Conc(; x, x) concatenates two copies of x.

The function PADRT(; x, y) = Conc(; x, ZEROES(; Msp(; y, x))) pads its argument x on the right with zeroes to length max(|x|, |y|).

Four functions

LOBIT(; x) = Lsp(; x, 1)
DELLOBIT(; x) = Msp(; x, 1)
HIBIT(; x) = Msp(; x, Msp(; x, 1))
DELHIBIT(; x) = Lsp(; x, Msp(; x, 1))

allow access to the rightmost and leftmost bits of a string.

The function 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. The similar function SHR(; x, y) = Lsp(; Msp(; x, y), x) truncates the rightmost |y| bits of x, filling the high bits with zeroes so the result is the same length as x.

The function

LEN(x; ) = \{ \begin{matrix}λ & if |x| = 0 \\ 1 & if |x| = 1 \\ Conc(; LEN(Fh(; x); ), 1) & if |x| > 1 \end{matrix}

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

The function

ROUNDUP(x; ) =

\{ \begin{matrix}1 & if |x| ≤ 1 \\ Conc(; ROUNDUP(Bh(; x); ), ROUNDUP(Bh(; x); )) & otherwise \end{matrix}

returns a string of 1’s whose length is the least power of 2 greater than or equal to |x|. Then EXTEND(x; ) = Lsp(; x, ROUNDUP(x; )) returns x padded on the left with zeroes up to power-of-2 length.

Since an ATM has random access to its input tapes, we need a function to implement random access. We define the function GETBIT(x; i) to return Bit(i, x), treating i as a binary number of length ⌈log(|x|)⌉; if i is shorter than that, we left-extend it with zeroes, and if longer, we ignore the leftmost bits.

GETBIT(x; i) = f_{1}(\begin{matrix}ROUNDUP(x; ); EXTEND(x; ), \\ Lsp(; i, DELLOBIT(; LEN(ROUNDUP(x; ); )))) \end{matrix}

where f_{1} is defined by simultaneous, very safe DCR as follows:

f_{1}(y; x, i) =
x  if y ≤ 1
Fh(; f_{1}(Fh(; y); x, i)) if y > 1 and HIBIT(; f_{2}(Fh(; y); x, i)) = 1
Bh(; f_{1}(Fh(; y); x, i)) if y > 1 and HIBIT(; f_{2}(Fh(; y); x, i)) = 0
f_{2}(y; x, i) = \{ \begin{matrix}PADRT(; i, x) & if |y| ≤ 1 \\ SHL(; Fh(; f_{2}(Fh(; y); x, i))), 1) & if |y| > 1 \end{matrix}

The reader may check that |f_{1}(y; x, i)| = |f_{2}(y; x, i)| for all y, x, i that arise in the computation of GETBIT, so by Lemma 12, GETBIT is in vsc(BASE).

The function

COPY(x; y) = \{ \begin{matrix}λ & if |x| = 0 \\ y & if |x| = 1 \\ Conc(; COPY(Fh(; x); y), COPY(Bh(; x); y)) & otherwise \end{matrix}

returns |x| copies of y. (A different definition of this function was used in Cobham (1965) to provide polynomial growth rates.)

By safe DCR on COPY, we can define

GROW(x, y; ) = \{ \begin{matrix}1 & if |x| = 0 \\ y & if |x| = 1 \\ COPY(y; GROW(Bh(; x), y; )) & otherwise \end{matrix}

This GROW function is in sc(BASE). Its length is |y|^{||x||}, so by Lemma 26, it is not in vsc(BASE).

Lemma 32. If t(|x⃗|) = O(log(|x⃗|)), then there is a function BLOWUP_{t}(x⃗; ) ∈ vsc(BASE) such that |BLOWUP_{t}(x⃗; )| ≥ 2^{t(|x⃗|)}.

If t(|x⃗|) = log^{O(1)}(|x⃗|), then there is a function BLOWUP_{t}(x⃗; ) ∈ sc(BASE) such that |BLOWUP_{t}(x⃗; )| ≥ 2^{t(|x⃗|)}.

Proof. The Conc function allows us to add the lengths of parameters, and combined with the constant function 1 it produces any desired linear growth rate. The COPY function allows us to multiply the length of a normal parameter by that of a safe one. By composition of these we can construct within vsc(BASE) a function BLOWUP(x⃗; ) whose length is any desired increasing polynomial of |x⃗|. This proves the first part of the lemma.

For the second part, we need not only polynomial but quasipolynomial growth rates, which are afforded by suitably many compositions of GROW. □

6.2. Arithmetizing an Alternating Machine. Our goal is to simulate the computation of an ATM within vsc(BASE) or sc(BASE). Throughout this section we shall assume the machine takes l inputs X_{1}, …, X_{l} and has k work tapes. Given such a machine and its time bound t(|X⃗|), we need to construct and evaluate a computation tree of depth t(|X⃗|). This takes several steps:

∘ Compute t(|X⃗|), rounding it up to an even number for technical reasons.

∘ Construct a full binary tree T_{0} of depth t(|X⃗|), each of whose leaves represents a distinct path through the computation tree.

∘ Recurse through T_{0}, determining whether each nonleaf node accepts by ANDing or ORing whether its children accept.

∘ At each leaf of T_{0}, extract the path encoded in that leaf and recurse through it to determine the ATM configuration at that leaf.

∘ Decide whether this leaf configuration accepts. For input configurations, this requires using GETBIT to read input.

For the sake of presentation, we shall go through these steps in reverse order.

We represent the configuration ⟨q, L_{1}, …, L_{k}, R_{1}, …, R_{k}⟩ of an ATM by a tuple of numbers, possibly defining functions from one configuration to another by simultaneous recursion. This is only valid if all the elements of the tuple are the same length, which is ensured by our assumption that each L_{i} and R_{i} have length exactly t(|X⃗|), the time bounds of the machine. We also pad the state q with zeroes to the same length; this is why we insist that t be at least the log of the number of states.

With this representation one can easily determine whether the state is an input state, and if so what input tape it reads, what work tape it uses as an index, and what symbol it expects to find on the input tape. Suppose, for example, it uses work tape 7 as an index to input tape 4, and accepts iff it reads a 0. Then the function

TEST_{7,4,0}(X⃗; q, L⃗, R⃗) = Not(; GETBIT(X_{4}; L_{7}))

returns a 1 iff this input configuration accepts. We can in fact define a function EVALLEAF(X⃗; C) ∈ vsc(BASE) to determine whether any given input configuration C accepts. (Some configurations in the tree may be leaves not because they are input configurations but because their children have been truncated by the time bound. In these cases, it makes no difference what EVALLEAF returns, since whether the tree accepts or rejects has already been determined.)

Similarly, one can test the state and what symbol is under each tape head by composing constantly many Cond and DELLOBIT functions, write and move on the tapes with SHL and SHR functions, and choose states by concatenating constants. By these means, we can define functions (or more properly, tuples of functions) NEXT_{1}(; q, L⃗, R⃗) and NEXT_{2}(; q, L⃗, R⃗) computing the two successor configurations of any given configuration. If ⟨q, L⃗, R⃗⟩ is an input configuration, we define both its successors to be ⟨q, L⃗, R⃗⟩ itself.

To find the configuration at a leaf of the computation tree, we must know the starting configuration of the ATM as well as the sequence of left/right decisions (henceforth called a “path”) it made on the way. The starting configuration is relatively easy to handle. The starting state q_{0} can be constructed by composing finitely many Conc and constant functions, and we can initialize each L_{i} and R_{i} to a blank work tape with ZEROES(; LEN(BLOWUP_{t}(X⃗; ); )). Thus, we can define a function (actually a tuple of functions) INIT(X⃗; ) to return the starting configuration of the machine.

As for the path, a natural representation is a string of 0’s and 1’s, with (say) the 0’s representing left branches and the 1’s right branches. For technical reasons, we shall “inflate” our paths, embedding the bits of interest in positions 0, 1, 3, 7, 15, … of an exponentially longer bit string.

Definition 33. The deflation of a bit-string x is the string y of length log(|x|) such that for all i, Bit(i, y) = Bit(2^{i} − 1, x).

Definition 34. An inflated path is a bit-string whose deflation is intended to be interpreted as a path.

Given an inflated path P and a starting configuration C, we find the input configuration at the end of the path as follows (still writing as one function what is really a tuple defined by simultaneous recursion):

GETLEAF(P; C) = \{ \begin{matrix}NEXT(; P, C) & if |P | ≤ 1 \\ NEXT(; P, GETLEAF(Bh(P); C)) & otherwise \end{matrix}

where NEXT(; P, C) = Cond(; HIBIT(; P), NEXT_{1}(; C), NEXT_{2}(; C)). At each step, NEXT examines the leftmost bit of the path and invokes NEXT_{1} or NEXT_{2} accordingly. GETLEAF then discards the left half of the inflated path (i.e., the leftmost bit of the path) and continues until the path is exhausted, at which point it returns the starting configuration.

Thus, if inputs X⃗ and an inflation P of path p are available as normal parameters, then EVALLEAF(X⃗; GETLEAF(P; INIT(X⃗; ))) returns 0 or 1, depending on whether the final state reached by the ATM along path p accepts or rejects. In order to determine whether the whole ATM accepts or rejects, we must apply this to each possible path p and combine the results with AND and OR as appropriate. We do this by constructing a binary tree T_{0} with an inflated path at each leaf, and performing very safe DCR on it: at each leaf of the binary tree, we call EVALLEAF(X⃗; GETLEAF(P; INIT(X⃗; ))) as above, and at each non-leaf stage, we either AND or OR the results of the two recursive calls, depending on whether the state is universal or existential.

To meet the requirements of very safe DCR, we must define a function H(; T, u_{1}, u_{2}), taking no normal parameters, which determines from a subtree T of T_{0} whether the corresponding state is universal or existential and thus whether to AND or OR the recursive results u_{1} and u_{2}. This is why we imposed the requirement in section 3.4 that the states of an ATM alternate strictly between universal and existential and start with an existential: the type of a non-leaf node in the computation tree is existential iff its distance from the root is even. We round t(|X⃗|) up to an even number, so the distance from the root is even iff the distance from the leaves, i.e., the height of the subtree T, is even. The height of the subtree is the log of the number of leaves in it, but this seems impossible to compute without recursion. Instead, we construct T_{0} so as to make the parity of the height of each subtree evident: for each subtree T, the height of T will be even iff the leftmost bits of its two children are equal.

Assuming we can construct a binary tree with all these properties, we define the {0, 1}-valued function EVALTREE(T, b, X⃗; ) by very safe DCR on a binary tree T of inflated paths as follows. The parameter b supplied to EVALTREE will be anything of the same length as an inflated path.

EVALTREE(T, b, X⃗; ) =

EVALLEAF(X⃗; GETLEAF(T; INIT(X⃗; )))  if |T | ≤ |b|;
EVALTREE(Fh(T), b, X⃗; ) ∧ EVALTREE(Bh(T), b, X⃗; )

if |T | > |b| and the height of T is odd; EVALTREE(Fh(T), b, X⃗; ) ∨ EVALTREE(Bh(T), b, X⃗; ) if |T | > |b| and the height of T is even.

To put this more formally,

EVALTREE(T, b, X⃗; ) =

\{ \begin{matrix}EVALLEAF(X⃗; GETLEAF(T; INIT(X⃗; ))) & if |T | ≤ |b|; \\ H(; T, EVALTREE(Fh(T), b, X⃗; ), EVALTREE(Bh(T), b, X⃗; )) & if |T | > |b|, \end{matrix}

where

H(; T, u_{1}, u_{2}) = Cond(; HIBIT(; T), Cond(; HIBIT(; Bh(T)), Or(; u_{1}, u_{2}), And(; u_{1}, u_{2})), Cond(; HIBIT(; Bh(T)), And(; u_{1}, u_{2}), Or(; u_{1}, u_{2}))).

The question remains: how do we get this binary tree of inflated paths? We need one inflation of each possible path through the ATM’s computation tree, and they must obey the right relationships: two siblings must represent paths differing only in the first bit, first cousins must represent paths differing in the first two bits, and so on. Furthermore, at each level of the tree, the two children must have equal high bits iff the height is even. All this is accomplished by the following function:

PATHS(Y; ) = \{ \begin{matrix}λ & if |Y | = 0; \\ Conc(; 0, 1) & if |Y | = 1; \\ H(; PATHS(Bh(; Y); )) & if |Y | > 1, \end{matrix}

where

H(; v) =

\{ \begin{matrix}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{matrix}

This PATHS function has many useful properties. First, PATHS(Y; ) = PATHS(ROUNDUP(Y; ); ), so in discussing it we can assume without loss of generality that |Y | is a power of two. Since |H(; v)| = 4|v|, we have |PATHS(Y; )| = 2 · 4^{log(|Y |)} = 2|Y |^{2}. We shall view PATHS(Y; ) as (the root of) a binary tree of depth ||Y || = 1 + log(|Y |), each node of which is the concatenation of its children, and each leaf of which is a string of length |Y |.

The less obvious properties of PATHS are presented in the following technical lemma.

Lemma 35. The binary tree represented by PATHS(Y; ) has the following properties:

∘ For any non-leaf node, the leftmost bits of its two children are equal iff the node’s height is even.

∘ The deflations of the leaf nodes comprise one copy of each of the possible bit-strings of length ||Y || = 1 + log(|Y |).

∘ Two leaves have a common ancestor of height i iff the rightmost ||Y || − i bits of their deflations are equal.

The proof of this lemma involves a number of straightforward but tedious inductions, and we omit it, but illustrate it with the first few values of PATHS, in which overbraces delimit the leaves: PATHS(λ; ) = λ, one leaf of length 0. PATHS(1; ) = ˆ0ˆ1, two leaves of length 1.

PATHS(11; ) = \overbrace{00} \overbrace{10} \overbrace{01} \overbrace{11}, four leaves of length 2.

PATHS(1111; ) = \overbrace{0000} \overbrace{1000} \overbrace{0010} \overbrace{1010} \overbrace{1111} \overbrace{0111} \overbrace{1101} \overbrace{0101}, eight leaves of length 4, each of which deflates to a distinct 3-bit path. PATHS(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 leaves of length 8, each of which deflates to a distinct 4-bit path. The reader is invited to verify the remaining properties in this example.

We put all this together with the following function:

SIMULATE(X⃗; ) = EVALTREE(\begin{matrix}PATHS(BLOWUP_{t}(X⃗; ); ), \\ Bh(; BLOWUP_{t}(X⃗; )), X⃗; \\ INIT(X⃗; )). \end{matrix}

This function determines whether the ATM, given input X⃗, accepts or rejects. Every part of its definition, with the possible exception of BLOWUP_{t}, has been by safe composition or very safe DCR. If t(|X⃗|) = O(log(|X⃗|)), then BLOWUP_{t} is in vsc(BASE), and therefore so is SIMULATE. If, on the other hand, t(|X⃗|) = log^{O(1)}(|X⃗|), then BLOWUP_{t} cannot be defined in vsc(BASE) but can be in sc(BASE), so SIMULATE is also in sc(BASE). We have proven the following lemma:

Lemma 36. For any log-time ATM with inputs X⃗, there is a function f(X⃗; ) ∈ vsc(BASE) that returns 1 if the machine accepts and 0 otherwise.

For any polylog-time ATM with inputs X⃗, there is a function f(X⃗; ) ∈ sc(BASE) that returns 1 if the machine accepts and 0 otherwise.

6.3. Comprehension. We have shown that any relation, i.e., any {0, 1}- valued function, in ALOGTIME (respectively APLOGTIME) is in vsc(BASE) (respectively sc(BASE)). But what of functions with values in {0, 1}^{∗}? The following lemma demonstrates that, so long as the length of the function value is a sufficiently slow-growing and easily computed function, the ability to compute each bit of a function enables us to compute its whole value at once.

Lemma 37. Let F (x⃗; ) be a tiered function. If there are functions f(i, x⃗; ) and SAME LENGTH_{F} (x⃗; ) in vsc(BASE) such that, for all x⃗,

∘ |F (x⃗; )| = |SAME LENGTH_{F} (x⃗; )|,

∘ for all i < |F (x⃗; )|, (f(i, x⃗; ) = Bit(i, F (x⃗; ))), and

∘ for all i ∈ {0, 1}^{∗}, f(i, x⃗; ) = f(Conc(; 0, i), x⃗; ),

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

The same holds with vsc(BASE) replaced throughout by sc(BASE).

Proof. We prove this by a simpler version of the “paths” technique used in section 6.2. We compute SAME LENGTH_{F} (x⃗; ), then generate a binary tree T whose leaves are the binary numbers (|SAME LENGTH_{F} (x⃗; )| − 1), …, 2, 1, 0, each embedded in a block of length ||SAME LENGTH_{F} (x⃗; )| − 1|.

COUNTDN(z; ) = f_{2}(z; LEN(z; ))

f_{1}(z; s) = \{ \begin{matrix}λ & if |z| = 0 \\ SHL(; ZEROES(; s), 1) & if |z| = 1 \\ TWIN(; SHL(; f_{1}(Bh(z); s), 0)) & if |z| > 1 \end{matrix}

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

We can then define F by very safe DCR as follows:

F (x⃗; ) = F′(\begin{matrix}COUNTDN(SAME LENGTH_{F} (x⃗; ); ), \\ LEN(SAME LENGTH_{F} (x⃗; ); ), x⃗; ) \end{matrix}
F′(T, b, x⃗; ) = \{ \begin{matrix}f(T, x⃗; ) & if |T | ≤ |b| \\ Conc(; F′(Fh(; T), b, x⃗; ), F′(Bh(; T), b, x⃗; )) & if |T | > |b| \end{matrix}

Since f is insensitive to leading zeroes, if T is the i-th leaf from the right then f(T, x⃗) = f(i, x⃗). The iterated function, Conc, is associative, so the effect is simply to concatenate the bits f(|b|−1, x⃗; ), f(|b|−2, x⃗; ), …, f(1, x⃗; ), f(0, x⃗; ). By the known properties of SAME LENGTH_{F} and f, this concatenation is precisely F (x⃗; ). □

7. Conclusions and Observations

The notion of classifying formal parameters into tiers by how they are used in computation has produced a number of simple characterizations of complexity classes. The project began with the introduction of tiering in Leivant (1990). The related second-order logical characterization of P in Leivant (1991) inspired the recursive-functions characterization of FP in Bellantoni & Cook (1992), which in turn inspired work on fast parallel classes in the present paper, and on the polynomial hierarchy and a form of linear space in Bellantoni (1992) (the latter result was independently proven in Handley 1992). Bellantoni, Leivant, and I all independently conjectured a “very safe” characterization of linear time; for one proof, see Bloch (1992).

Leivant has pointed out that all these characterizations depend on viewing the universe of data as a free (or nearly so) algebra, and that the differences among the characterizations of APLOGTIME, P, and linear space are primarily differences in the choice of this algebra. Since the three algebras involved could be called the three simplest algebras suitable for representing computational data, we conclude that these three complexity classes are foundationally extremely natural. Indeed, Otto (1992) has recast the results of Bellantoni & Cook into category theory, suggesting that the class is natural even in an extremely abstract setting with no notion of computation.

An obvious direction for further research is to find other complexity classes that are characterized by tiered recursion over a simple algebra, and eventually to determine in general what classes have such characterizations and thus may be considered foundationally “natural classes.” Similarly, one may ask how properties of the algebra relate to the complexity classes they characterize.

An alternate interpretation of very safe recursion is as safe recursion with a prohibition on nested applications. A natural question, then, is what complexity classes arise from allowing a fixed nesting depth greater than one. Bellantoni (1992) counted nestings of minimization to produce characterizations of the levels of the Polynomial Hierarchy, and it seems that similar techniques could distinguish infinite hierarchies within polynomial time or polylog space.

30  Stephen Bloch

Acknowledgements

This work began at the 1991 Conference on Proof Theory, Complexity and Arithmetic, which I attended on NSF/ČSAV grant INT-8914569 through the efforts of Sam Buss and Gaisi Takeuti. Further work was supported by the University of Manitoba and Judy Goldsmith’s NSERC grant OGP0121527.

I would like to thank Sam Buss, Judy Goldsmith, and an anonymous referee for many helpful suggestions, both technical and expository. Discussions with Stephen Bellantoni and Daniel Leivant also helped illuminate the subject.

References

William Allen, Arithmetizing uniform NC. Annals of Pure and Applied Logic 53(1) (1991), 1–50. See also Divide and Conquer as a Foundation of Arithmetic, Ph.D. thesis, University of Hawaii at Manoa, 1988.

Toshiyasu Arai, Frege systems, ALOGTIME and bounded arithmetic. Manuscript, 1992.

D.A. Barrington, Bounded-width polynomial-size branch programs recognize exactly those languages in NC^{1}. J. Comput. Sys. Sci. 38(1) (1989), 150–164. See also Proc. Eighteenth Ann. ACM Symp. Theor. Comput., ACM Press 1986, 1–5.

David A. Mix Barrington, Quasipolynomial size circuit classes. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference. IEEE Computer Society Press, 1992, 86–93.

Stephen Bellantoni, Predicative Recursion and Computational Complexity. PhD thesis, University of Toronto, 1992.

Stephen Bellantoni and Stephen Cook, A new recursion-theoretic characterization of the polytime functions. computational complexity 2 (1992), 97–110.

Stephen Bloch, Alternating function classes within P. Technical Report 92-16, University of Manitoba Computer Science Dept, 1992.

Samuel R. Buss, Bounded Arithmetic. Number 3 in Studies in Proof Theory. Bibliopolis (Naples), 1986. See also “The polynomial hierarchy and bounded arithmetic” in Proc. Seventeenth Ann. ACM Symp. Theor. Comput., ACM Press 1985, 285–290.

Samuel R. Buss, The boolean formula value problem is in ALOGTIME. In Proc. Nineteenth Ann. ACM Symp. Theor. Comput., 1987, 123–131.

Function-Algebraic Characterizations  31

A. Chandra, D. Kozen, and L. Stockmeyer, Alternation. J. Assoc. Comput. Mach. 28(1) (1981), 114–133.

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

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

Peter Clote and Gaisi Takeuti, Bounded arithmetic for NC, ALogT IME, L and NL. Annals of Pure and Applied Logic 56 (1992), 73–117.

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

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

W.G. Handley, Bellantoni and Cook’s characterization of polynomial time functions. Typescript, 1992.

Daniel Leivant, Subrecursion and lambda representation over free algebras. In Feasible Mathematics, ed. Samuel Buss and Philip Scott, Perspectives in Computer Science, 281–291. Birkhäuser, 1990.

Daniel Leivant, A foundational delineation of computational feasibility. In Proc. Sixth IEEE Conf. Logic in Computer Science. IEEE Computer Society Press, 1991.

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

James Otto, A category-theoretic characterization of polytime. Contributed talk at MSI Feasible Mathematics Conference, 1992.

W. Ruzzo, On uniform circuit complexity. J. Comput. Sys. Sci. 22 (1981), 365–383.

Manuscript received 16 December 1992

Stephen Bloch Department of Computer Science 915 Patterson Office Tower University of Kentucky Lexington, KY 40506–0027

sbloch@s.ms.uky.edu