
## 5.4 Circuit Complexity

For the next impossibility result we need the notions of *boolean circuits* and *families of circuits*.

A **boolean circuit** is a directed, acyclic graph C V ; E , where the nodes V are called **gates**.

Each gate v V has a type type v f:; ; ; ; x1; x2; : : : . The gates with type v
; ; x1 ; x2; : : : have in-degree zero, the gates with type v f:g have in-degree one, and the gates with type v f^; _g have in-degree two. All gates except one have at least one outgoing edge. The gate with no outgoing edge is called the **output gate**. The gates with no incoming edges are called the **input gates**. The **depth** of a circuit is the length of the longest path from an input gate to the output gate. The **size** of a circuit is the number of gates in the circuit.

Given a *value assignment* to the variables x1; x2; : : : , the circuit computes the value of the output gate in the obvious way. For example, for x1 and x2 we get the value 1 at the output gate of the circuit shown in Figure 4.

![0_image_0.png](0_image_0.png)

Instead of using circuits for computing boolean functions, we can also use them for accepting words of length n in ;?. A word w x1 : : : xn ;nis now interpreted as a value assignment to the n input variables x1; : : : ; xn of a circuit. The word is **accepted** iff the output gate has value 1 for this word. In order to deal with words of different length, we need one circuit for each possible length. A **family of circuits** is an infinite sequence C C0; C1; : : : , where Cn has n input variables. The language accepted by such a family of circuits is the set of words w such that Cjjwjj accepts w.

Usually, one considers so-called **uniform** families of circuits, i.e., circuits that can be generated on a Turing machine with a log n-space bound. Sometimes, however, also non-uniform families are interesting. For example, the class of languages accepted by non-uniform families of polynomiallysized circuits is just the class P/poly introduced in Section 5.2.

Using restrictions on the size and depth of the circuits, we can now define new complexity classes, which in their uniform variants are all subsets of P. One class that is important in the following is the class of languages accepted by uniform families of circuits with polynomial size and logarithmic depth, named NC1. Another class which proves to be important for us is defined in terms of non-standard circuits, namely circuits with gates that have *unbounded fan-in*. Instead of restricting the in-degree of each gate to be two at maximum, we now allow an unbounded in-degree.

The class of languages accepted by families of polynomially sized circuits with unbounded fan-in and constant depth is called AC0.