The Depth Hierarchy: NC, AC, and the Cost of Wide Gates

Depth is the circuit resource that maps onto time in a parallel machine, and the hierarchy built on it is the closest thing complexity theory has to a working classification of parallel difficulty. The classes are defined by two independent choices — whether gates have bounded or unbounded fan-in, and what depth is permitted — and the interleaving between the two families is where most of the structural results live.

The four definitions

$\mathrm{NC}^i$ contains the languages decided by circuit families of polynomial size and $O(\log^i n)$ depth, with gates of fan-in two from a complete basis. $\mathrm{AC}^i$ replaces fan-in two with unbounded fan-in, and its gates are AND and OR (NOT is free, by pushing negations to the leaves). $\mathrm{TC}^i$ adds majority gates to $\mathrm{AC}^i$. All three are non-uniform by default; the uniform versions require the circuit description to be computable in logarithmic space, and the classes then coincide with familiar ones.

The base of the hierarchy is where the definitions bite.

$\mathrm{NC}^0$ with bounded fan-in and constant depth depends on only $O(1)$ inputs, since a depth-$d$ fan-in-two circuit has at most $2^d$ leaves. It computes exactly the functions whose output is determined by a fixed-size window of the input, and it is strictly below $\mathrm{AC}^0$.

$\mathrm{AC}^0$ with unbounded fan-in and constant depth computes addition, comparison, and every function expressible as a fixed-depth Boolean formula of arbitrary width. It does not compute parity, and the switching lemma is the proof.

$\mathrm{TC}^0$ adds majority and thereby computes parity, since parity of $n$ bits reduces to majority by a constant-depth construction that compares counts. Whether $\mathrm{TC}^0$ is strictly below $\mathrm{NC}^1$ is open.

Interleaving, and why the two families do not coincide

The conversion from wide to narrow gates gives $\mathrm{AC}^i \subseteq \mathrm{NC}^{i+1}$ for every $i$: replace each fan-in-$k$ gate with a binary tree of depth $\lceil \log_2 k \rceil$, which is at most $\lceil \log_2 n \rceil$ for polynomial-size circuits. So the $\mathrm{AC}$ hierarchy sits inside the $\mathrm{NC}$ hierarchy one level up.

The conversion from narrow to wide is immediate, since a fan-in-two gate is a fan-in-two wide gate: $\mathrm{NC}^i \subseteq \mathrm{AC}^i$. Combined, the two inclusions give

$$\mathrm{NC}^i \subseteq \mathrm{AC}^i \subseteq \mathrm{NC}^{i+1}.$$

The chain is the entire known relationship. No strictness is established anywhere in it except at the very bottom, where $\mathrm{NC}^0 \subsetneq \mathrm{AC}^0$ follows from the parity separation and from the input-dependence argument.

import math

def depth_after_binarisation(depth, max_fan_in):
    """Worst-case depth when every wide gate becomes a balanced binary tree."""
    return depth * math.ceil(math.log2(max_fan_in)) if max_fan_in > 1 else depth

# A depth-3 AC circuit with fan-in n becomes depth 3*ceil(log2 n) after
# binarisation, which is inside NC^2 only when the original depth is 1.
# For depth 2 the result is O(log n), i.e. NC^1, not NC^2.

The arithmetic in the comment is the whole interleaving argument in miniature, and it also shows why the inclusion is not reversible by the same trick: narrowing cannot be undone without a bound on how many gates a level may contain, and the number of gates is not part of the depth.

The collapse that would follow from NC1 = NC

The hierarchy is defined with polynomial size, and that choice is load-bearing. If $\mathrm{NC}^1 = \mathrm{NC}$ — that is, if every polynomial-size polylog-depth circuit could be simulated at logarithmic depth — then the hierarchy collapses to its first level, because padding and composition let any $\mathrm{NC}^i$ circuit be simulated by an $\mathrm{NC}^1$ circuit on a larger input.

The argument is a composition lemma. A circuit of depth $\log^i n$ is a tree of $\log^{i-1} n$ levels, each of which is itself an $\mathrm{NC}^1$-computable function on a block of inputs. Composing the two simulations costs a logarithm of the block size at each level, and the logarithms add rather than multiply only when the inner simulation is at logarithmic depth. So $\mathrm{NC}^i \subseteq \mathrm{NC}^{i-1}$ follows from the hypothesis, and iterating gives the collapse.

The same shape of argument explains why $\mathrm{NC}$ is defined as the union over all $i$ of polynomial-size polylog-depth circuits rather than as a class with a fixed depth bound. Without the union, the class would depend on an arbitrary cutoff, and the natural questions — is a given problem parallelisable — would have no stable answer.

The bottom of the hierarchy, in detail

The separations that are proved are all at the first two levels, and each rests on a different argument.

$\mathrm{NC}^0 \ne \mathrm{AC}^0$ is the easiest. The OR of $n$ bits is in $\mathrm{AC}^0$ as a single gate and cannot be in $\mathrm{NC}^0$ because no constant-depth fan-in-two circuit reads more than constantly many inputs. This is a syntactic argument about the number of leaves, not a combinatorial one.

$\mathrm{AC}^0 \ne \mathrm{TC}^0$ follows from parity. Parity is in $\mathrm{TC}^0$ by a majority-based construction and outside $\mathrm{AC}^0$ by the switching lemma. The separation is unconditional and is one of the few strict inclusions in the whole of circuit complexity.

$\mathrm{AC}^0 \ne \mathrm{NC}^1$ follows because parity is in $\mathrm{NC}^1$ with $O(n)$ gates and depth $O(\log n)$ — a balanced XOR tree — and outside $\mathrm{AC}^0$. This is the strongest unconditional statement at the bottom and it does not extend upward: nothing is known about $\mathrm{TC}^0$ versus $\mathrm{NC}^1$, and nothing is known about $\mathrm{NC}^1$ versus $\mathrm{NC}^2$.

Uniform versions and the connection to space

The uniform hierarchy is where depth connects to sequential resources, and the connection is exact rather than approximate.

$\mathrm{NC}^1$ under logarithmic-space uniformity equals the class of languages decided by alternating Turing machines with logarithmic space and constant alternation depth, by the correspondence between circuit depth and alternation. The full class of logarithmic-space languages, $\mathrm{L}$, contains $\mathrm{NC}^1$ and is contained in $\mathrm{NC}^2$; whether either inclusion is strict is open. So the depth hierarchy is a refinement of the space hierarchy at the low end, and the non-uniform version is what makes the refinement meaningful: uniformity is what ties depth to a machine, and non-uniformity is what lets the lower bounds be proved.

Barrington’s theorem sharpens the picture in a surprising direction. The word problem for any finite non-solvable group — deciding whether a product of generators equals the identity — is complete for $\mathrm{NC}^1$ under constant-depth reductions, and it is computable by a branching program of constant width and polynomial length. The theorem equates $\mathrm{NC}^1$ with polynomial-length constant-width branching programs, which is a statement about a sequential model with a very small state space. The depth of a circuit and the width of a branching program are the same resource viewed from two directions, and the equivalence is why $\mathrm{NC}^1$ occupies a special position: it is the smallest class that contains a complete problem for a natural sequential model.

What depth costs in practice

Two conversions dominate the practical reading of the hierarchy, and both are quantitative.

Binarisation multiplies depth by $\lceil \log_2 k \rceil$ where $k$ is the maximum fan-in. For a circuit with fan-in $n$ and depth 2, the result is depth $2 \log n$, which is $\mathrm{NC}^1$; for depth 3 the result is $3 \log n$, still $\mathrm{NC}^1$ in the asymptotic accounting because the constant multiplies the logarithm. The inclusion $\mathrm{AC}^i \subseteq \mathrm{NC}^{i+1}$ is therefore generous for constant $i$: a circuit of constant depth and polynomial fan-in binarises to depth $O(\log n)$, which lies in $\mathrm{NC}^1$ regardless of how many gates each level holds. The hierarchy’s levels are separated by the exponent of the logarithm, not by the constant, and a constant-factor depth increase never changes the level.

Adding gates to reduce depth has the opposite cost. A function computable at depth $d$ with size $s$ can generally be computed at depth $d-1$ only with a size increase, and the increase is what the size-depth tradeoff results quantify. For parity, the tradeoff is essentially tight: a circuit of depth $d$ needs size $2^{\Omega(n^{1/(d-1)})}$, so reducing depth from $\log n$ to a constant costs an exponential in size. That single tradeoff explains why addition is easy in parallel and multiplication is not known to be, and why the hierarchy has resisted separation for four decades.