Theory of Computational Complexity, 2nd Edition

Chapter 6

Circuit Complexity

We introduce in this chapter Boolean circuits as a nonuniform computational model. We demonstrate a close relation between the notion of Circuit-size complexity and TM time complexity. Two important exponential lower bound results are proved. The exponential lower bound for monotone circuits is proved by the technique of combinatorial approximation, and the exponential lower bound for constant-depth circuits is proved by the probabilistic method. The NC hierarchy is introduced as a model for computational complexity of parallel computation. The related notion of P-completeness is also presented.

6.1 Boolean Circuits

A Boolean circuit is an acyclic digraph of which each node with no in-edge is labeled by a variable or a Boolean constant 0 or 1 and each other node is labeled by a Boolean operator: negation, disjunction (OR), or conjunction (AND). The nodes labeled by variables are the input nodes, and the nodes labeled by Boolean operators are called logical gates. For each logical gate, its fan-in is the number of its in-edges (or inputs) and its fan-out is the number of its out-edges. We do not restrict the fan-out of a gate, but we sometimes restrict the fan-in of a gate. For a circuit computing a Boolean function, we assume that there exists a unique node of the circuit that has no out-edge; this node gives the output of the circuit and is called the output gate. Given a Boolean assignment to the variables, the circuit computes the function ...