Circuit complexity

A circuit is a model for computing Boolean functions, in which functions are computed using a sequence of elementary operations, called gates. Different circuit models exist, depending on how they restrict the width, depth, size, and pool of usable gates. The circuit size, or circuit complexity of a family of Boolean functions [math]\{f_n\}_n[/math], deals with how the size of the smallest circuit computing [math]f_n[/math] grows as [math]n \to \infty[/math].

General definition

A circuit which computes a Boolean function is a tuple [math](L, G)[/math], where

• [math]L[/math] is a set of gate labels, each of which is a function from [math]\{-1,1\}^{i}[/math] to [math]\{-1,1\}[/math] for some non-negative integer [math]i[/math] (where [math]i[/math] represents the number of inputs to the gate), and
• [math]G[/math] is a labelled directed acyclic graph with labels from [math]L[/math].

The vertices of the graph are called gates. For each gate [math]g[/math] of in-degree [math]i[/math], the gate [math]g[/math] can be labeled by an element [math]\ell[/math] of [math]L[/math] if and only if [math]\ell[/math] is defined on [math]\{-1,1\}^{i}[/math].

Terminology

The gates of in-degree 0 are called inputs or leaves. The gates of out-degree 0 are called outputs. If there is an edge from gate [math]g[/math] to gate [math]h[/math] in the graph [math]G[/math] then [math]h[/math] is called a child of [math]g[/math]. We suppose there is an order on the vertices of the graph, so we can speak of the [math]k[/math]th child of a gate when [math]k[/math] is less than the out-degree of the gate.

The size of a circuit is the number of nodes of a circuit. The depth of a gate [math]g[/math] is the length of the longest path in [math]G[/math] beginning at [math]g[/math] up to an output gate. In particular, the gates of out-degree 0 are the only gates of depth 1. The depth of a circuit is the maximum depth of any gate.

Level [math]i[/math] is the set of all gates of depth [math]i[/math]. A levelled circuit is a circuit in which the edges to gates of depth [math]i[/math] comes only from gates of depth [math]i + 1[/math] or from the inputs. In other words, edges only exist between adjacent levels of the circuit. The width of a levelled circuit is the maximum size of any level.

Evaluation

The exact value [math]V(g)[/math] of a gate [math]g[/math] with in-degree [math]i[/math] and label [math]l[/math] is defined recursively for all gates [math]g[/math].

[math] V(g) = \begin{cases} l & \text{if } g \text{ is an input} \\ l(V(g_1), \dotsc, V(g_i)) & \text{otherwise,} \end{cases} [/math]

where each [math]g_j[/math] is a parent of [math]g[/math].

The value of the circuit is the value of each of the output gates.

AC⁰

For a fixed positive integer [math]d[/math], let AC⁰_d be all families of circuits with depth exactly [math]d[/math], size polynomial in [math]n[/math], unlimited fan-in AND and OR gates, and NOT gates at the inputs. The class AC⁰ is the union of AC⁰_d over all [math]d[/math], i.e it is the class of all constant depth, polynomial-sized circuits which use AND and OR gates.

Randomness

We say a function [math]g: \{-1, 1\}^n \times \{-1, 1\}^r \rightarrow \{-1, 1\}[/math] is a randomized function for [math]f:\{-1, 1\}^n \rightarrow \{-1, 1\}[/math] if

[math] P_{r}[g(x, r) = f(x)] \geq 1/3 [/math]

Where r is drawn from the uniform distribution.

A randomized circuit is a circuit implementing a randomized function. A circuit C is a randomized circuit for a function f if it implements a randomized function for f.

Randomized circuits can be simulated by deterministic circuits with a size increase of only [math]O(n)[/math] using Adleman's Theorem . To actually perform this derandomization, it requires to at least compute Promise Majority. Promise majority only requires a depth 3 monotone AC⁰ circuit. Thus converting a randomized circuit to a deterministic one only costs polynomial size and small circuit depth for most common circuit classes.

One thing to note about Adleman's theorem is that it produces pseudorandom inputs non uniformly. That is the derandomization is non explicit. Finding pseudorandom generators (PRGs) with log seed length even for AC⁰ is still open. Although many polylogarithmic seed length PRGs for AC⁰ are known .

Nondeterminism

We say a function [math]g: \{-1, 1\}^n \times \{-1, 1\}^m \rightarrow \{-1, 1\}[/math] is a certificate verifier for function [math]f:\{-1, 1\}^n \rightarrow \{-1, 1\}[/math] with certificate length m if

[math] \exists c: g(x, c) \iff f(x) [/math]

Such a c causing g to accept is the certificate of x for g. We say that a circuit, C, implementing a certificate verifier for a function, f, is a nondeterministic circuit for f. Polynomial sized non deterministic circuits are the complexity class NP/poly.

It can be shown that any non deterministic circuit can be implemented with constant depth by an alternating circuit with only constant size overhead in the following way:

Let C be a non deterministic circuit implementing [math]g: \{-1, 1\}^n \times \{-1, 1\}^m \rightarrow \{-1, 1\}[/math]. We make a circuit A with certificate length [math]m + |C|[/math] which expects as a certificate for x the certificate c for g, then the output of every gate in C when run on x and c. Then the circuit just computes what the output of every gate should be and verifies every gate output calculated agrees with the claimed output AND the final output is accept.

Thus limited depth polynomial sized non deterministic circuits are not usually studied.

Properties

• TODO: There is vast literature on the relation between different complexity measures: Bounded depth circuit size, Fourier tail, noise sensitivity, etc. Start citing, please!