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)$, although this result is not covered in the course).

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 $s^{4s} < 2^{2^n}$, 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)$.

Suppose we have a boolean formula in CNF computing $\mathsf{PARITY}$ as a conjunction of clauses $C _ i$.

Suppose that some clause $C _ i$ had fewer than $n$ literals, and let $x$ be some literal that does not occur in the clause. Consider a setting of the other literals in the clause that falsifies the clause, and hence makes the parity $0$.

For this setting, the value of parity does not depend on the value of the variable $x$, which is the assumption that the CNF computes parity.

Now suppose that there are fewer than $2^{n-1}$ clauses. Each clause with $n$ literals is only false on one assignment to the $n$ variables and the CNF needs to be false on $2^{n-1}$ assignments to compute the parity.

@example~ @sheets~

By the results in lectures, we have two bounds:

• Lower bound: For every $N$, there exists a Boolean function $f$ that requires circuits of size at least $\frac{2^N}{10N}$ to calculate.
• Upper bound: Every Boolean function (and so in particular $f$) can be computed using circuits of size at most $10N \cdot 2^N$.

Fix some $k$ and let $N = (k+1) \log _ 2 n$. Then there is some $f : {0, 1}^n \to {0, 1}$ which requires circuits of size at least $\frac{2^N}{10N} = \frac{n^{k+1}}{10(k+1) \log _ 2 n} = O(n^{k})$. Then let $f’ : {0, 1}^N \to {0, 1}$ be the function which applies $f$ on the first $N$ bits of $x$, hence $f’$ also requires circuits of size $O(n^{k})$.

But then $f’$ can be computed with circuits of size $2^N 10 N = n^{k+1}10(1 + \frac{1}{k}) \log n$ and hence $f’$ can be computed with circuits of size $\Omega(n^{k+2})$.

By taking $n$ sufficiently large, we see that there exists some $f’$ which:

• Can be computed by circuits of size $n^{k+2}$, but
• Can’t be computed by circuits of size $n^k$

as required.

---

Alternative proof: Consider a subset $S$ of $\lbrace 0, 1 \rbrace^n$ chosen uniformly at random from all sets of size $n^{k+1}$. Define the Boolean function $f _ S$ such that $f _ S(x) = 1$ iff $x \in S$.

For every $S$ of size $n^{k+1}$, $f _ S$ can be computed in size $n^{k+2}$ by taking a big OR of size $n^{k+1}$ over $C _ y$ for $y \in S$, where $C _ y$ is a circuit of size $n$ checking if $x = y$.

To see that $f _ S$ does not have circuits of size $n^k$, we use a counting argument. By previous results, there are at most $(n^k)^{4(n^k)} = n^{4kn^k}$ Boolean functions computed by circuits of size $n^k$.

On the other hand, there are at least ${ { 2^n } \choose {n^{k+1} } } \ge 2^{n^{k+1} }$ Boolean functions $f _ S$ (this estimate is for the restricted class of functions we are considering). Hence for large enough $n$, there is a Boolean function $f _ {S(n)}$ not computable by circuits of size $n^k$. We then define our Boolean function $f$ to be $f _ {S(n)}$ on inputs of length $n$.

@example~ @sheets~

\[\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.

---

Shorter “snapshot” proof from CCAMA: 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} = \lbrace 1^n \mid n\text{'s binary expansion encodes halting TM} \rbrace\]

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}$.

We prove this by showing under the assumption $\mathsf{NP}$ has polynomial-size circuits, $\Pi _ 2\mathsf{SAT} \in \Sigma^p _ 2$.

Fix some instance $\varphi = \forall \pmb x \exists \pmb y \text{ } \varphi’$ of $\Pi _ 2 \mathsf{SAT}$.

Claim: $\varphi$ is a YES-instance iff there exists a circuit $D _ m$ of size $m^k$ such that for all $x$, $D _ m(\varphi(x, \cdot))$ outputs a satisfying assignment to $\varphi(x, \cdot)$, where “$\cdot$” denotes the variables that are the input to the formula.

In other words, $x \in \varphi$ iff $\exists D _ m \forall x \text{ }R(D _ m, x, \varphi)$ where the quantifiers are appropriately polynomially bounded. Note that this predicate can be decided in polynomial time and this gives an algorithm for solving $\Pi _ 2\mathsf{SAT}$ in $\Sigma^p _ 2$.

By the assumption, we may assume that there is a sequence of polynomial-size circuits $\lbrace C _ m \rbrace$ of size $m^k$ which output a satisfying assignment to an input formula $\varphi$ of size $m$ if $\varphi$ is satisfiable.

For the forward implication, if $\varphi$ is a YES instance, for every $x$, $\varphi(x, \cdot)$ is satisfiable. By the correctness of the circuits $C _ m$, taking $D _ m = C _ m$ is a valid guess for which $D _ m(\varphi(x, \cdot))$ always outputs a satisfying assignment, and hence we are done.

For the backward implication, if there is a $D _ m$ such that for each $x$, $D _ m(\varphi(x, \cdot))$ outputs a satisfying assignment, then for each $x$, $\varphi(x, \cdot)$ is satisfiable, which implies that for each $x$, there exists $y$ such that $\varphi(x, y)$ holds, and hence $\varphi$ is a YES-instance.

We may choose $m$ to be a fixed polynomial in the number of clauses of $\varphi$ and the length of $y$.

@example~ @sheets~

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

$\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 $\lbrace C _ n\rbrace$ 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.