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 and are a special kind of circuits; a formal language 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 in digital electronics.
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, or be entirely described by binary NAND gates. 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 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. 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.[1] The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.[2]
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.[3]
Footnotes
Cite error: Invalid <references> tag;
parameter "group" is allowed only.
<references />, or <references group="..." />References
- Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.
| P ≟ NP | This theoretical computer science-related article is a stub. You can help ssf by expanding it. |
