boolean circuit

the Boolean circuit is a model of computation which is a generalization of boolean formulas and a simplified model of the silicon chips used to make modern computers. it is a natural model for nonuniform computation.
[cite:;taken2 from @computability_arora_2009 chapter 6 boolean circuits]

a basis is a finite set consisting of boolean functions and families of boolean functions.
[cite:;taken from @complexity_vollmer_2016 chapter 1.2 circuit size and depth; definition 1.5]

$\text{[math]}$ is the standard bounded fan-in basis.
$\text{[math]}$ is the standard unbounded fan-in basis.
$\text{[math]}$ is the basis of constants and boolean functions of 1 or 2 variables.

[cite:;taken from @complexity_vollmer_1999 definition 1.12]

let $\text{[math]}$ be a basis. a boolean circuit over $\text{[math]}$ with $\text{[math]}$ inputs and $\text{[math]}$ outputs is a tuple
$\text{[math]}$ where $\text{[math]}$ is a finite directed acyclic graph, $\text{[math]}$ is an injective function, $\text{[math]}$ , and $\text{[math]}$ , such that the following conditions hold:

if $\text{[math]}$ has in-degree 0, then $\text{[math]}$ or $\text{[math]}$ is a 0-ary boolean function (i.e. a boolean constant) from $\text{[math]}$ .
if $\text{[math]}$ has in-degree $\text{[math]}$ , then $\text{[math]}$ is a $\text{[math]}$ -ary boolean function from $\text{[math]}$ or a family of boolean functions from $\text{[math]}$ .
for every $\text{[math]}$ , $\text{[math]}$ , there is at most one node $\text{[math]}$ such that $\text{[math]}$ .
for every $\text{[math]}$ , $\text{[math]}$ , there is exactly one node $\text{[math]}$ such that $\text{[math]}$ .

if $\text{[math]}$ has in-degree $\text{[math]}$ and out-degree $\text{[math]}$ , then we say: $\text{[math]}$ is a gate in $\text{[math]}$ with fan-in $\text{[math]}$ and fan-out $\text{[math]}$ . if $\text{[math]}$ is a gate in $\text{[math]}$ then we also write $\text{[math]}$ instead of $\text{[math]}$ . if $\text{[math]}$ then we say: $\text{[math]}$ is a wire in $\text{[math]}$ ; more specifically we say that $\text{[math]}$ is an input wire of $\text{[math]}$ and an output wire of $\text{[math]}$ ; and that $\text{[math]}$ is a predecessor gate of $\text{[math]}$ . if $\text{[math]}$ for some $\text{[math]}$ then $\text{[math]}$ is an input gate or input node. if $\text{[math]}$ then $\text{[math]}$ is an output gate or output node.
[cite:;taken from @complexity_vollmer_2016 chapter 1.2 circuit size and depth; definition 1.6]

arora's gives a somewhat different definition:

for every $\text{[math]}$ , an $\text{[math]}$ -input, single-output boolean circuit is a directed acyclic graph with $\text{[math]}$ sources (vertices with no incoming edges) and one sink (vertex with no outgoing edges). all nonsource vertices are called gates and are labeled with one of $\text{[math]}$ or $\text{[math]}$ . the vertices labeled with $\text{[math]}$ and $\text{[math]}$ have fan-in (i.e., the number of incoming edges) equal to 2 and the vertices labeled with $\text{[math]}$ have fan-in 1. the size of $\text{[math]}$ , denoted by $\text{[math]}$ , is the number of vertices in it.
if $\text{[math]}$ is a boolean circuit, and $\text{[math]}$ is some input, then the output of $\text{[math]}$ on $\text{[math]}$ , denoted by $\text{[math]}$ , is defined in the natural way. more formally, for every vertex $\text{[math]}$ of $\text{[math]}$ , we give it a value $\text{[math]}$ as follows: if $\text{[math]}$ is the $\text{[math]}$ th input vertex then $\text{[math]}$ and otherwise $\text{[math]}$ is defined recursively by applying $\text{[math]}$ 's logical operation on the values of the vertices connected to $\text{[math]}$ . the output $\text{[math]}$ is the value of the output vertex.
[cite:;taken from @computability_arora_2009 definition 6.1]

though this definition restricts fan-in to 2, this is essentially without loss of generality since a $\text{[math]}$ or $\text{[math]}$ gate with fan-in $\text{[math]}$ can be easily repaced with a subcircuit consisting of $\text{[math]}$ gates of fan-in 2.
[cite:;taken from @computability_arora_2009 chapter 6.1 boolean circuits and $\text{[math]}$ ]

a circuit $\text{[math]}$ with $\text{[math]}$ inputs and $\text{[math]}$ outputs computes a function
$\text{[math]}$ this is formalized in the following definition.

[cite:;refer to @complexity_vollmer_2016 chapter 1.2 circuit size and depth; definition 1.7]

complexity theorists usually pay special attention to 0-1-valued functions, because they can be interpreted as characteristic functions of some set of words.

if $\text{[math]}$ is a circuit with one output gate, i.e., $\text{[math]}$ computes the characteristic function of some broken link: blk:def-lang $\text{[math]}$ , then we say: $\text{[math]}$ accepts $\text{[math]}$ . if $\text{[math]}$ such that $\text{[math]}$ then we also say: $\text{[math]}$ accepts $\text{[math]}$ .
[cite:;taken from @complexity_vollmer_2016 definition 1.9]

a single circuit computes only a finite function, i.e., a function with finite domain and range. as an example, for every $\text{[math]}$ the function $\text{[math]}$ from [cite:;in @complexity_vollmer_2016 chapter 1.1 an example: addition] is finite. if a circuit accepts a language $\text{[math]}$ , then $\text{[math]}$ must be finite ( $\text{[math]}$ for some $\text{[math]}$ ). however, generally we are interested in infinite functions; e.g., we want to add numbers of arbitrary length or we want to build acceptors for arbitrary, possibly infinite sets. a circuit however by definition has a fixed finite number of inputs and outputs. thus we will have to consider different circuits for different input lengths. therefore we consider circuit families.

let $\text{[math]}$ be a basis. a circuit family over $\text{[math]}$ is a sequence $\text{[math]}$ , where for every $\text{[math]}$ , $\text{[math]}$ is a boolean circuit over $\text{[math]}$ with $\text{[math]}$ inputs. let $\text{[math]}$ be the function computed by $\text{[math]}$ . then we say that $\text{[math]}$ computes the function $\text{[math]}$ , defined for every $\text{[math]}$ by
$\text{[math]}$ we write $\text{[math]}$ and $\text{[math]}$ . we say that $\text{[math]}$ accepts $\text{[math]}$ if and only if $\text{[math]}$ computes $\text{[math]}$ . in this context we also use the notation $\text{[math]}$ (where $\text{[math]}$ ) and $\text{[math]}$ . if $\text{[math]}$ is a circuit family then we use the notation $\text{[math]}$ for the function computed by $\text{[math]}$ .
[cite:;taken from @complexity_vollmer_2016 definition 1.10]

let $\text{[math]}$ be a boolean circuit over $\text{[math]}$ . the size of $\text{[math]}$ is defined to be the number of non-input gates in $\text{[math]}$ , i.e., $\text{[math]}$ , and the depth of $\text{[math]}$ is defined to be the length of a longest directed path in the graph $\text{[math]}$ .
let $\text{[math]}$ be a circuit family, and let $\text{[math]}$ . $\text{[math]}$ has size $\text{[math]}$ and depth $\text{[math]}$ if for every $\text{[math]}$ , $\text{[math]}$ has size $\text{[math]}$ and depth $\text{[math]}$ .
[cite:;taken from @complexity_vollmer_2016 definition 1.11]

let $\text{[math]}$ be a basis, and let $\text{[math]}$ . we define the following complexity classes:

$\text{[math]}$ is the class of all sets $\text{[math]}$ for which there is a circuit family $\text{[math]}$ over basis $\text{[math]}$ of size $\text{[math]}$ that accepts $\text{[math]}$ .
$\text{[math]}$ is the class of all sets $\text{[math]}$ for which there is a circuit family $\text{[math]}$ over basis $\text{[math]}$ of depth $\text{[math]}$ that accepts $\text{[math]}$ .
$\text{[math]}$ is the class of all sets $\text{[math]}$ for which there is a circuit family $\text{[math]}$ over basis $\text{[math]}$ of size $\text{[math]}$ and depth $\text{[math]}$ that accepts $\text{[math]}$ .
$\text{[math]}$ is the class of all functions $\text{[math]}$ for which there is a circuit family $\text{[math]}$ over basis $\text{[math]}$ of size $\text{[math]}$ that computes $\text{[math]}$ .
$\text{[math]}$ is the class of all functions $\text{[math]}$ for which there is a circuit family $\text{[math]}$ over basis $\text{[math]}$ of depth $\text{[math]}$ that computes $\text{[math]}$ .
$\text{[math]}$ is the class of all functions $\text{[math]}$ for which there is a circuit family $\text{[math]}$ over basis $\text{[math]}$ of size $\text{[math]}$ and depth $\text{[math]}$ that computes $\text{[math]}$ .

in the case where we have the basis $\text{[math]}$ we simply omit the index, that is $\text{[math]}$ , etc. in the case where the basis $\text{[math]}$ is $\text{[math]}$ we omit the index but we prefix the class with "Unb", e.g., we write $\text{[math]}$ for $\text{[math]}$ .
[cite:;taken from @complexity_vollmer_2016 definition 1.13]

[cite:;taken from @complexity_vollmer_2016 chapter 1.2 circuit size and depth]

given any circuit with NOT gates, we can use demorgan to "push back" all NOTs to the inputs so that there are no NOT gates in the circuit anymore beside those that are applied to the input gates. this property is sometimes exploited and NOT gates are ignored and our circuits would only consist of OR and AND gates.

for every broken link: blk:def-str $\text{[math]}$ there is some boolean circuit of size $\text{[math]}$ with $\text{[math]}$ inputs such that given a string $\text{[math]}$ it returns 1 if $\text{[math]}$ and 0 otherwise.

let $\text{[math]}$ for some $\text{[math]}$ , for every $\text{[math]}$ from 1 to $\text{[math]}$ , we define a literal
$\text{[math]}$ in other words we have $\text{[math]}$ iff $\text{[math]}$ . now consider the trivial circuit that computes $\text{[math]}$ .

this can be used to show a trivial but weak bound on the size complexity of circuits of $\text{[math]}$ variables:

for every $\text{[math]}$ for some $\text{[math]}$ we have $\text{[math]}$ .

given an input $\text{[math]}$ , consider the circuit defined by
$\text{[math]}$ where the equality $\text{[math]}$ is checked by the $\text{[math]}$ circuit from boolean_circuit.html. since we have $\text{[math]}$ possible permutations of $\text{[math]}$ we can have an equality circuit for each which would give us a boolean circuit of total size $\text{[math]}$ .

a better (but not the best) upper bound of $\text{[math]}$ can be achieved:

function decomposition: $\text{[math]}$ . observe that
$\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ . thus
$\text{[math]}$ apply the decomposition recursively to $\text{[math]}$ and $\text{[math]}$ . generally at step $\text{[math]}$ ,
$\text{[math]}$ where $\text{[math]}$ . since $\text{[math]}$ is a constant at the $\text{[math]}$ step, $\text{[math]}$ is an upper bound on the circuit size of $\text{[math]}$ .
BROKEN

a stronger upper bound is found in BROKEN. the following lemma proposes a worst-case complexity upper bound for any sufficiently complex boolean functions, as some boolean simpler functions can have size complexity that is as low as $\text{[math]}$ .

let $\text{[math]}$ , we have $\text{[math]}$ for sufficiently large $\text{[math]}$ .

the following lemma is equivalent:

let $\text{[math]}$ , and let $\text{[math]}$ , then there is atleast $\text{[math]}$ functions whose circuit size complexity is atleast $\text{[math]}$ .
[cite:;found in @complexity_jukna_2012 theorem 1.14]
[cite:;found in @complexity_vollmer_1999 theorem 1.47]
BROKEN

for every $\text{[math]}$ , the number of circuits of size $\text{[math]}$ with $\text{[math]}$ inputs is at most $\text{[math]}$ .

we show that every such circuit can be described by a string of $\text{[math]}$ bits. this would show that the number of those circuits is at most the total number of the possible strings. given some circuit we describe it by $\text{[math]}$ blocks of strings each block of length $\text{[math]}$ at most.
for every gate $\text{[math]}$ in the circuit we use a block with:

which vertex is the first with an edge to the gate $\text{[math]}$ . the circuit contains $\text{[math]}$ vertices: $\text{[math]}$ gates, $\text{[math]}$ input gates of the form $\text{[math]}$ and $\text{[math]}$ input gates of the form $\text{[math]}$ . hence to represent the vertex we need $\text{[math]}$ bits.
we apply the same thing to the second vertex ( $\text{[math]}$ more bits).
which function does $\text{[math]}$ compute (1 bit).
whether $\text{[math]}$ is at all present in the circuit, as there can be less than $\text{[math]}$ gates (1 bit).

in total we need $\text{[math]}$ bits.

if we substitute in this claim $\text{[math]}$ we get that the number of circuits of this size is at most
$\text{[math]}$ and so the number of functions with size complexity greater than $\text{[math]}$ is atleast $\text{[math]}$ .

every $\text{[math]}$ can be computed by circuits with $\text{[math]}$ gates over the basis $\text{[math]}$ .
[cite:;taken2 from @complexity_vollmer_1999 theorem 1.51]

for a circuit $\text{[math]}$ , $\text{[math]}$ denotes the size of $\text{[math]}$ .
let $\text{[math]}$ be a basis. for a boolean function $\text{[math]}$ , we define:
$\text{[math]}$ we may simply write $\text{[math]}$ if the basis is known from context or is simply a standard basis.
[cite:;taken from @complexity_vollmer_1999 definition 3.1]

for a circuit $\text{[math]}$ , $\text{[math]}$ denotes the depth of $\text{[math]}$ .
let $\text{[math]}$ be a basis. for a boolean function $\text{[math]}$ , we define:
$\text{[math]}$ we may simply write $\text{[math]}$ if the basis is known from context or is simply a standard basis.

a boolean circuit of depth $\text{[math]}$ with one output gate has a most $\text{[math]}$ intermediary gates and $\text{[math]}$ input gates. to receive $\text{[math]}$ we need $\text{[math]}$ . for every $\text{[math]}$ we have $\text{[math]}$

the following remains an open question:

is there a function $\text{[math]}$ that is computable by a boolean formula in polynomial size? the best known until today: $\text{[math]}$ such that $\text{[math]}$ , i.e. $\text{[math]}$ .

for every functions $\text{[math]}$ with $\text{[math]}$ ,
$\text{[math]}$ [cite:;taken2 from @computability_arora_2009 theorem 6.22]

diagonalization methods do not seem to apply in this setting; nevertheless, we are able to prove the theorem using shannon's counting argument. to show the idea, we prove that $\text{[math]}$ .
by boolean_circuit.html, for every $\text{[math]}$ , there is a function $\text{[math]}$ that is not computable by $\text{[math]}$ -sized circuits. on the other hand, by boolean_circuit.html, every function from $\text{[math]}$ to $\text{[math]}$ is computable by a $\text{[math]}$ -sized circuit.
therefore, if we set $\text{[math]}$ and let $\text{[math]}$ be the function that applies $\text{[math]}$ on the first $\text{[math]}$ bits of its input, then
$\text{[math]}$ [cite:;taken2 from @computability_arora_2009 theorem 6.22]