A Boolean circuit is a mathematical model of computation

Computation

Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

 used in studying computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

. Boolean circuits are the main object of study in circuit complexity

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....

 and are a special kind of circuit

Circuit (computer theory)

A circuit in computer theory is a theoretical structure simulating electrical and data paths, in which voltage and binary values enter at the beginning of the circuit, go through gates which do some computation and output an answer. An important special case of circuits is the boolean...

s; a formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

 can be decided by a family of Boolean circuits, one circuit for each possible input length. In addition, they are used as a formal model for combinational logic

Combinational logic

In digital circuit theory, combinational logic is a type of digital logic which is implemented by boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the...

 in digital electronics.

Boolean circuits are defined in terms of the gates

Logic gate

A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...

 they contain. For example, a circuit might contain binary

Binary function

In mathematics, a binary function, or function of two variables, is a function which takes two inputs.Precisely stated, a function f is binary if there exists sets X, Y, Z such that\,f \colon X \times Y \rightarrow Z...

 AND and OR gates and unary

Unary

* Unary numeral system, the simplest numeral system to represent natural numbers* Unary operation, a kind of mathematical operator that has only one operand* Unary coding, an entropy encoding that represents a number n with n − 1 ones followed by a zero...

 NOT gates, or be entirely described by binary NAND gate

NAND gate

The Negated AND, NO AND or NAND gate is the opposite of the digital AND gate, and behaves in a manner that corresponds to the opposite of AND gate, as shown in the truth table on the right. A LOW output results only if both the inputs to the gate are HIGH...

s. Each gate corresponds to some Boolean function that takes k bits as input and 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 of a family, for example, 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 (complexity)

In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...

. 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 a circuit can be computed from its index, 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

Directed acyclic graph

In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

. 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. The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.

Evaluation of a circuit

The problem CIRCUIT-EVAL takes as input the description of a Boolean circuit and a truth assignment to the variables of the circuit, and accepts only if the circuit evaluate to true. CIRCUIT-EVAL is P-complete

P-complete

In complexity theory, the notion of P-complete decision problems is useful in the analysis of both:# which problems are difficult to parallelize effectively, and;# which problems are difficult to solve in limited space....

.