Formula Size and the Tree-Shaped Restriction on Circuits

A formula is a circuit with no fan-out. Every gate output feeds exactly one other gate, so the underlying graph is a tree rooted at the output and the leaves are literals. Nothing is computed twice and nothing is shared. The restriction looks like a minor bookkeeping detail and is in fact the difference between a problem whose lower bounds are stuck near linear size and one whose lower bounds reach cubic.

The tree, and the measure

A de Morgan formula over variables $x_1, \ldots, x_n$ is a binary tree whose leaves are literals — a variable or its negation — and whose internal nodes are $\wedge$ or $\vee$. The size of the formula is the number of leaves; some authors count internal nodes instead, which differs by exactly one, and the two conventions agree up to the constant that matters in asymptotic statements.

Size is the only resource. There is no depth bound in the definition, so a formula may be a long chain or a balanced tree, and the two shapes compute the same function with the same leaf count. The difference appears only when depth is bounded, and then balanced formulas become the natural object: a formula of size $s$ can always be balanced to depth $O(\log s)$ by the standard centroid argument, at the cost of duplicating some subformulas.

Two facts connect formulas to circuits and both are worth stating at the outset. Every formula is a circuit, so circuit size is at most formula size for every function. And every circuit of size $s$ converts to a formula of size $O(s^2)$ by unwinding: each gate that is used $k$ times is copied $k$ times, and the sum of the copy counts over the circuit is bounded by the number of paths, which is quadratic in $s$. Both directions matter, because they place formula size between circuit size and its square.

def formula_size(tree):
    """tree is nested tuples: ('lit', name) or (op, left, right).
    Returns (leaves, internal_nodes)."""
    if tree[0] == 'lit':
        return 1, 0
    _, left, right = tree
    l_leaves, l_inner = formula_size(left)
    r_leaves, r_inner = formula_size(right)
    return l_leaves + r_leaves, l_inner + r_inner + 1

# A formula over n variables that mentions each variable once is read-once;
# its leaf count is exactly n and no function it computes can be a parity
# on more than n bits, because parity requires every variable at least once.

Why sharing is worth a quadratic factor

The unwinding bound is tight in the worst case, and the function that witnesses it is multiplication-like: a circuit computes many partial results that are consumed repeatedly, and a formula must recompute each one along every path that reaches it.

Consider a circuit that computes $n$ outputs, each depending on all $n$ inputs, by first computing a shared intermediate value $v$ and then combining $v$ with each output’s private logic. The circuit pays for $v$ once. A formula has no way to reference $v$ from two places, so it pays for $v$ once per output, and the total is $n$ times the cost of $v$.

The upper bound of $O(s^2)$ is achieved by the path-counting argument: for each gate $g$, let $c(g)$ be the number of distinct paths from $g$ to the output, so $c(\text{output}) = 1$ and $c(g)$ is the sum of $c$ over $g$‘s consumers. Unwinding produces a formula whose size is $\sum_g c(g)$, and since each $c(g) \le s$ and there are $s$ gates, the sum is at most $s^2$. The bound can be improved by distinguishing gates that feed more than one consumer: cutting the fan-out at those gates splits the circuit into pieces each of which unwinds cheaply, and the total over all pieces is $O(s^{1.5})$ for the standard construction. The crude $s^2$ figure is the one usually quoted because it needs no case analysis, and it is what makes the gap between circuit and formula size at most quadratic in the worst case. The bound is not tight for every circuit; circuits whose fan-out is concentrated near the output unwind much more cheaply.

Proving a formula lower bound by weighting edges

The standard technique for formula size is not counting but potential. Khrapchenko’s method assigns a weight to pairs of inputs that the formula separates and derives a lower bound from the weight of a single gate.

The construction: let $A$ be the set of inputs on which $f$ outputs 0 and $B$ the set on which it outputs 1. Consider the bipartite graph between $A$ and $B$ in which $(a,b)$ is an edge when $a$ and $b$ differ in exactly one coordinate. Khrapchenko’s bound says the formula size of $f$ is at least the product of the average degrees of the two sides, which for a regular graph with $|A| = |B| = 2^{n-1}$ and degree $n$ gives $n^2$.

Parity attains it. For parity, $A$ and $B$ are the even and odd weight strings, each of size $2^{n-1}$, and every string has exactly $n$ neighbours across the partition, so the bound is $n \cdot n = n^2$. Since a chain of XOR gates with a linear number of gates is a circuit but not a formula, the quadratic formula lower bound and the linear circuit upper bound coexist without contradiction: parity has formula size $\Theta(n^2)$ and circuit size $O(n)$.

The bound is proved by induction over the formula, and the inductive step is where the tree structure is used. For a leaf, the graph has a single edge or none and the bound holds. For an $\vee$ gate with children $f_1$ and $f_2$, the 1-inputs split between them, and the edge set of $f$ is contained in the union of the edge sets of the children together with cross edges; the weight of the union is bounded by the sum of the weights plus a cross term that is controlled by Cauchy-Schwarz. The absence of fan-out is what makes the split exhaustive: every 1-input is produced by exactly one child, with no input counted twice. In a circuit with sharing, the same input can be produced along several paths and the induction fails.

Cubic bounds, and what the extra power costs

Khrapchenko’s method saturates at $n^2$ for any function whose bipartite graph is regular, and parity is the natural example. Going beyond required a different function and a different technique.

Andreev’s function composes a decision problem on the first half of the variables with a lookup indexed by the second half. Its de Morgan formula size is $n^{3-o(1)}$, established by Håstad by refining a technique of Andreev and building on the shrinkage method: a random restriction that fixes a fraction of the variables makes a formula of size $s$ collapse, with high probability, to a formula of size roughly $s^{1/2}$ on the surviving variables, because each surviving gate has both children surviving with probability bounded away from one and the tree prunes geometrically. Iterating the restriction and combining the collapse with a hardness measure for the restricted function yields the cubic bound.

The exponent in the shrinkage method is a property of the basis. For de Morgan formulas the shrinkage exponent is exactly 2, which is why the restriction halves the exponent of the size at each round; for formulas over a basis containing XOR, the exponent is different and the corresponding bounds are weaker. This is a concrete instance of the basis dependence that disappears for unrestricted circuits but returns whenever a structural restriction is imposed.

Restriction round, informally:

  formula F of size s on n variables
      restrict each variable with probability p  ->  F' on ~pn variables
      with probability 1 - s^{-Theta(1)}:  |F'| <= s^{1/2 + o(1)}
      and F' still computes a hard function on its variables
  repeat until the variable count is constant

Where formulas sit among the classes

Because every formula is a circuit, a circuit lower bound implies a formula lower bound, and the converse fails. The interesting direction is the conversion. Since a circuit of size $s$ yields a formula of size $O(s^2)$, a superquadratic formula lower bound for a function in $\mathrm{P}$ would separate $\mathrm{P}$ from $\mathrm{NC}^1$ only if the function’s circuit size were also large, which is exactly what is not known.

The classes line up as follows. Polynomial-size formulas with unbounded depth are exactly $\mathrm{NC}^1$ when balanced, by the balancing lemma: a formula of size $s$ becomes a formula of depth $O(\log s)$ with a constant-factor size increase. So formula size and $\mathrm{NC}^1$ are the same measure up to polynomial factors, and the depth hierarchy inherits the formula results. A function with formula size $n^{\omega(1)}$ is outside $\mathrm{NC}^1$; the known cubic bound for Andreev’s function is not enough to place it outside, since cubic is still polynomial.

Read-once formulas, where each variable appears at most once, are a stricter class and are decidable in polynomial time: a read-once formula over a complete basis computes a function whose set of prime implicants has a tree structure, and that structure can be recovered from the truth table. The gap between read-once and general formulas is another instance of the same theme — adding the ability to reuse a variable is what turns a tractable structural question into an open lower-bound problem.

The cost of removing sharing

Formulas are the natural model for hardware that cannot route a signal to two destinations, and for straight-line programs with no register reuse. The price of that restriction is a blow-up in the worst case and a different set of techniques in the best case. For unrestricted circuits the best explicit bound is linear in $n$; for de Morgan formulas it is cubic, which is a stronger exponent but applies to a smaller class, so the two numbers are not directly comparable. The gap is not a difference in technique alone: the tree structure is what lets the restriction argument prune, and pruning is what makes the cubic bound provable. The switching lemma uses the same pruning idea against depth rather than against fan-out, and the two methods share their central obstacle: both prove bounds by making the circuit simpler under a random restriction, and both stop working when the circuit can compute parity cheaply.