Boolean circuit

A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

Boolean circuits are defined in terms of the gates they contain. For example, a circuit might contain binary AND and OR gates and unary NOT gates. Each gate corresponds to some Boolean function, meaning that it is some mathematical function which takes "k" bits as input and which outputs a single bit.

Several important complexity measures can be defined on Boolean circuits, including circuit depth, circuit size, and number of alternations. In a circuit family, we consider the size complexity, for example, of a family to be the function of n that gives the size of the circuit that decides inputs of length n.

Several important complexity classes are defined in terms of Boolean circuits, including NC. NC is defined to be the set of Boolean functions that can be decided by uniform Boolean circuits of polynomial size and polylogarithmic depth. Here the word "uniform" means that there must be some condition on the circuit family so that a description of the n'th circuit can be computed from the number n.

Formal definition

In giving a formal definition of Boolean circuits, Vollmer starts by defining a basis set "B" of Boolean functions, corresponding to the gates allowable in the circuit model. A Boolean circuit over a basis "B", with "n" inputs and "m" outputs, is then defined as a finite directed acyclic graph. Each vertex corresponds to either a basis function or one of the inputs, and there are a set of exactly "m" nodes which are labeled as the outputs. [Vollmer 1999, p. 8.] The edges must also have some ordering, to distinguish between different arguments to the same Boolean function. [Vollmer 1999, p. 9.]

Footnotes