Computational Complexity HT25, Boolean circuits

A directed acyclic graph with $n$ sources (inputs) and one sink (output), where each non-source vertex is a gate ($\text{AND}$, $\text{OR}$, $\text{NOT}$).

It has two input wires.

$C$ is an infinite list of circuits $C _ 0, C _ 1, \ldots$ where $C _ n$ has $n$ variables. $C$ decides $L$ if for every string $w$, $w \in L$ iff $C _ { \vert w \vert }(w) = 1$.

The number of gates it contains, not counting $\text{NOT}$ gates.

The length of the longest path from an input variable to the output.

No circuit with fewer gates is equivalent to it.

The function $f : \mathbb N \to \mathbb N$ where $f(n)$ is the size of $C _ n$ (note that this exact rather than asymptotic; this makes sense as there are no nice “speedup” theorems for circuit).

The size complexity of a minimal circuit family for that language.

The depth complexity of a depth-minimal circuit family for that language.

We can compute $\text{parity} _ 2$ using a $\text{XOR}$ gate. Then a binary tree structure can be used to combine several of the $\text{XOR}$ results together.

@example~

The class of languages decidable by polynomial-sized circuit families, i.e.

\[\mathsf P_{/\mathsf{poly} } = \bigcup_{c} \mathsf{SIZE}(n^c)\]

A boolean formula is a boolean circuit where each gate has fan-out at most one.

Every Boolean function on $n$ bits has circuits of size $O(n 2^n)$ (and in fact of size $O(2^n / n)$).

Note that every Boolean function on $n$ bits can be converted into a DNF of size $O(n 2^n)$ by adding each row of the corresponding truth table that evaluates to one to the formula. Since there are $2^n$ possible rows, and each one has size at most $n$, it follows the DNF is of size $O(n 2^n)$.

Then this DNF formula can be converted into a circuit where each term is a tree of $n-1$ $\text{AND}$ gates, and the disjunction over terms is transformed into a tree of $\text{OR}$ gates of size at most $2^n$.

There exists a Boolean function on $n$ bits that requires circuits of size $\Omega(2^n / n)$, and a $1 - o(1)$ fraction of Boolean functions $f$ on $n$ bits require circuits of size at least $2^n / (10n)$.

Since $\text{NOT}$ gates are not counted in the size of a circuit, we may assume by De Morgan’s laws that the $\text{NOT}$ gates only appear at the input level. Hence we may assume that any circuit is instead over $2n$ input literals $x _ i$ and $\overline{x _ i}$.

We encode a Boolean circuit of size $s$ by a list of $s$ tuples $(i, t, c _ 1, c _ 2)$ where:

• $i$ is the index of a gate/variable (hence $i \le s$)
• $t$ is the “type” of the tuple:
  • If $t = 1$, then the tuple represents an $\text{AND}$ gate
  • If $t = 2$, then the tuple represents an $\text{OR}$ gate
  • If $3 \le t \le 2n + 2$, then the tuple represents a variable
  • (hence $t \le 2n + 2$)
• If $t = 1$ or $t = 2$, then $c _ 1$ and $c _ 2$ are the inputs to the gate; otherwise they are irrelevant (hence $c _ 1, c _ 2 \le s$).

Any Boolean circuit of size $s$ can be represented by a list of such tuples, and any such list corresponds to at most one Boolean circuit. Hence the number of Boolean circuits of size $s$ is at most the number of possible tuples, which is at most $(s^{3}(2n + 2))^s$.

When $s \ge 2n + 2$, this is at most $s^{4s}$.

The number of distinct Boolean functions on $n$ bits is $2^{2^n}$, by considering truth tables. Hence when $2^{2^n} > s^{4s}$, it follows that there is a Boolean function with no circuits of size $s$, since a circuit of size $s$ computes a single Boolean function.

When $s^{4s} < 2^{2^n} / n$, it follows that there is at least a $1 - 1/n$ fraction of Boolean functions on $n$ bits requiring circuits of size greater than $s$, and this inequality holds for $s = 2^n / (10n)$.

\[\mathsf P \subseteq \mathsf P_{/\mathsf{poly} }\]

We need to show that for every language $L \in \mathsf P$, there exists a polynomial-sized circuit family $\lbrace C _ n \rbrace _ {n \in \mathbb N}$ such that $C _ n$ correctly recognises $L$.

---

Tableau-based proof:

Let $M = (Q, \Sigma, \Gamma, \delta, q _ 0, q _ \text{accept}, q _ \text{reject})$ decide $L$ in time $T(n)$, and let $w$ be an input of length $n$ to $M$. Define a tableau for $M$ on $w$ to be a $T(n) \times T(n)$ table whose rows are configurations of $M$.

We may assume that $M$ accepts only when its head is on the leftmost tape cell and that cell is blank. We may also assume that once $M$ has halted, it stays in that configuration until it reaches $T(n)$ time steps.

The $i$th row of the tableau contains the configuration at the $i$th step of the computation as the contents of the tape, and the position of the current tape head is marked by a composite character $\widetilde{q _ k 0}$ or $\widetilde{q _ k 1}$ to denote that $M$ is in state $q _ k$ and it is over the marked character.

Let $\text{cell}[i, j]$ denote the $i$th row and $j$th column. By the assumptions above, we can determine whether $M$ has accepted by considering $\text{cell}[T(n), 1]$.

The content of each cell is determined by values of three cells in the preceding row: if we know $\text{cell}[i-1, j-1], \text{cell}[i-1, j]$ and $\text{cell}[i-1, j+1]$, we may obtain the value of $\text{cell}[i, j]$ by considering $M$’s transition function (the fact we need $\text{cell}[i-1, j]$ is obvious, but we need the other cells to handle the case where the pointer is over them and we move left or right).

Now we construct the circuit $C _ n$. It has several gates for each cell in the tableau, these gates compute the value at a cell from the values of the three cells that affect it.

Let $k$ be the number of elements in $\Gamma \cup (Q \times \Gamma)$. We create $k$ “lights” for each cell in the tableau, one light for each member of $\Gamma$, and one light for each member of $(Q \times \Gamma)$, for a total of $kt^2(n)$ lights. Name these $\text{light}[i, j, s]$ where $1 \le i, j \le T(n)$ and $s \in \Gamma \cup (Q \times \Gamma)$.

The condition of the lights in the cell indicates the contents of that cell: if $\text{light}[i, j, s]$ is active then symbol $s$ is in position $(i, j)$.

Suppose that if the cells $\text{cell}[i-1, j-1], \text{cell}[i-1, j]$ and $\text{cell}[i-1, j+1]$ contain $a, b$ and $c$ respectively, $\text{cell}[i, j]$ contains $s$ according to $\delta$. Wire the circuit so that if $\text{light}[i-1, j-1, a], \text{light}[i-1, j, b]$ and $\text{light}[i-1, j+1, c]$ are on, then so is $\text{light}[i, j, s]$. Do this by connecting the three lights at the $i-1$ level to a $\mathsf{AND}$ gate whose output is connected to $\text{light}[i, j, s]$.

There might be several different settings $(a _ 1, b _ 1, c _ 1), \ldots, (a _ l, b _ l, c _ l)$ of $\text{cell}[i-1, j-1]$, $\text{i-1, j}$ and $\text{cell}[i-1, j+1]$ such that $\text{cell}[i, j]$ contains $s$. In this case, wire the circuit so that we take an $\mathsf{OR}$ over all the possibilities before attaching it to the light.

For cells at the left or right boundaries of the tableau, only wire them to the cells which affect their contents.

For the cells in the first row, we wire their lights to the input variables, so that $\text{light}[1, 1, \widetilde{q _ 0 1}]$ is connected to $w _ 1$, and likewise $\text{light}[1, 1, \widetilde{q _ 0 0}]$ is connected through a $\mathsf{NOT}$ gate to $w _ 1$. Likewise the rest of the initial lights are connected to the inputs $w _ 2, \ldots, w _ n$ and $\text{light}[1, k, \sqcup]$ is set to $1$ for each $n < k \le T(n)$. The rest of the lights in the front row are off.

Since $M$ accepts $w$ if it is in an accept state $q _ \text{accept}$ on a cell containing $\sqcup$ at the left end of the tape at step $T(n)$, we may designate $\text{light}[T(n), 1, \widetilde{q _ \text{accept} \sqcup}]$ is set.

---

Short “snapshot” proof, vaguely non-constructive: Let $M$ be an $O(T(n))$-time machine for deciding $L$. We may assume that $M$ is oblivious, i.e. that is head movements do not depend on the input but only depend on the input length. So it suffices to show that every oblivious TM has a $O(T(n))$-sized circuit family $\lbrace C _ n \rbrace _ {n \in \mathbb N}$ such that $C _ n(x) = M(x)$ for every $x \in \lbrace 0, 1 \rbrace^n$.

Let $x \in \lbrace 0, 1 \rbrace^\ast$ be some input for $M$ and define the transcript of $M$’s execution on $x$ to be the sequence $z _ 1, \ldots, z _ {T(n)}$ of snapshots

\[z_i = \langle \text{state of }M, \text{symbol under each head}\rangle\]

of the execution at each step in time.

We may encode each snapshot $z _ i$ by a constant-sized binary string, and furthermore, we can compute the string $z _ i$ based on the input $x$, the previous snapshot $z _ {i-1}$ and the snapshots $z _ {i _ 1}, \ldots, z _ {i _ k}$ where $z _ {i _ j}$ denotes the last step that $M$’s $j$th head was in the same position as it is in the $i$th step, i.e.

\[z_i = f(z_{i-1}, z_{i_1}, \ldots, z_{i_k})\]

Because there are only a constant number of strings of constant length (each $ \vert z _ i \vert = ( \vert Q \vert + \vert k \vert )(k+1)$, this means that we can compute $z _ i$ from the previous snapshots using a constant-sized circuit.

(why is this possible? Because $M$ is oblivious, each $i _ 1, \ldots, i _ k$ depend only on $i$ and not the input $x$. $z _ {i-1}$ gives all the information about the current state and the symbols under the tape heads, and we need $z _ {i _ 1}, \ldots, z _ {i _ k}$ so that if we move left or right onto a new cell, we can report what that cell is. Note that $z _ {i _ j}$ is the last step that $M$’s $j$th head was in the same position as it was after completing the transition in the $i$th step).

The composition of all these constant-sized circuits give rise to a circuit that computes from the input $x$ the snapshot $z _ {T(n)}$ of the last step of $\tilde M$’s execution on $x$. There is a simple constant-sized circuit that given $z _ {T(n)}$, outputs $1$ iff $z _ {T(n)}$ is an accepting snapshot (in which $M$ outputs $1$ and halts). Thus there is an $O(T(n))$-sized circuit $C _ n$ such that $C _ n(x) = M(x)$ for every $x \in \lbrace 0, 1 \rbrace^n$.

This is a logspace reduction, i.e. each circuit $C _ n$ can be constructed in logarithmic space given $1^n$ (we may write the circuit description as we go, repeatedly iterating over the description of $M$).

This shows that $\mathsf P \subseteq \mathsf P^u _ {/\mathsf{poly} }$ where $\mathsf P^u _ {/\mathsf{poly} }$ is the class of languages decidable by logspace-uniform circuit families of polynomial size. To see that $\mathsf P^u _ {/\mathsf{poly} } \subseteq \mathsf P$, consider the TM which just computes the circuit and then executes it.

Hence $\mathsf P = \mathsf P^u _ {/\mathsf{poly} }$.

Consider

\[\mathsf{UHALT} = \\{1^n \mid n\text{'s binary expansion encodes halting TM} \\}\]

then $\mathsf{UHALT}$ has constant sized circuits, but is undecidable and in particular, not in $\mathsf P$.

This result says that all problems in $\mathsf P$ have polynomially-sized circuits. Hence if there is some language in $\mathsf{NP}$ which does not have polynomial size circuits, it follows that $\mathsf P \ne \mathsf{NP}$.

\[\mathsf{CVP} = \\{\langle C, x\rangle \mid C \text{ Boolean circuit that evaluates to }1\text{ on }x\\}\]

$\mathsf{CVP}$ is $\mathsf P$-hard: Let $L \in \mathsf P$ be a language with corresponding polynomial time decider $M$. Since $\mathsf P \subseteq \mathsf P _ {/\mathsf{poly} }$, $L$ has polynomial-sized circuits $\{C _ n\}$ and the proof that $\mathsf P \subseteq \mathsf P _ {/\mathsf{poly} }$ establishes that $C _ n$ can be constructed in logarithmic space given $1^n$.

Hence there is a log-space m-reduction $f$, which given $x$, computes $C _ { \vert x \vert }$ from $1^{ \vert x \vert }$ in logarithmic space and outputs $\langle C _ { \vert x \vert }, x\rangle$, hence this is an m-reduction.

$\mathsf{CVP}$ is in $\mathsf P$: Given a circuit $C$ and input $x$, sort the gates of $C$ in topological order, and then evaluates the gates in increasing order, storing the value at each gate. Since any gate can be evaluated in constant time given its input values, this takes polynomial time in total.

There is a logspace computable function mapping $1^n$ to the description of the circuit $C _ n$.

$\mathsf P$ is the class of languages decided by logspace-uniform circuits of polynomial size.