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.

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 ...

Start Free Trial

No credit card required