46 Boolean Circuits

• A boolean circuit is like a formula, but where we can reuse sub-formulas.
• Equivalently, it is well-founded diagram built from boolean gates.
• The boolean formulas are just circuits whose underlying graph is a tree.

Definition

An $n$-input Boolean circuit $C$ is a directed acyclic graph with:

• $n$ sources $x_1,\cdots ,x_n$ (vertices with no incoming edges)
• one sink $s$ (vertex with no outgoing edges)
• a labelling from non-source vertices to $\{\neg ,\wedge ,\vee \}$ (called gates)
• vertices labelled $\neg$ have fan-in (i.e., number of incoming edges) 1;
• vertices labelled $\wedge$ or $\vee$ have fan-in 2

The size of C, written $|C|$, is its number of vertices.

Example

Here is a circuit $C$ that computes the binary exclusive-or $\oplus$:

• $C$ has vertices $x_1,x_2,1,2,3,4,s$ with sources $x_1,x_2$ and sink $s$
• $C$ has edges:
  • $(x_1,1),(x_1,4),(x_2,2),(x_3,3),(1,3),(2,4),(3,s),(4,s)$
• $C$ has labelling $1\mapsto \neg ,2\mapsto \neg ,3\mapsto \wedge ,4\mapsto \wedge ,5\mapsto \vee$

Computation

Since a circuit $C$ is a directed acyclic graphs (dag), given an assignment $b:\{x_1,\cdots ,x_n\}\to \{0,1\}$ we may define the value $b(v)$ at a note $v$ by induction on the structure of $C$:

• ($b(x_i)$ is already defined).
• if a non-source node $v$ is labelled with $\neg$ with incoming edge from a node $u$, then $b(v):=1-b(u)$
• if a non-source node $v$ is labelled $\vee$ with incoming edges from nodes $u_0$ and $u_1$, then $b(v):=\min (b(u_0),b(u_1))$
• if a non-source node $v$ is labelled $\wedge$ with incoming edges from nodes $u_0$ and $u_1$, then $b(v):=\min (b(u_0),b(u_1))$

From here, we can define the output $b(C)$ of $C$ as just $b(s)$.

Example

Complexity Matters

Note that the inductive definition of ‘output’ yields a polynomial-time algorithm for evaluating circuits:

Proposition

The set of pairs $(C,b)$ where

• $C$ is an $n$-input circuit; and
• $b:\{0,1{\}}^n\to \{0,1\}$ such that $b(C)=1$ is in P

In fact the ‘circuit value problem’ is actually complete for P, under logspace-reduction.