Notes - Computational Complexity HT25, Boolean circuit model

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

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.

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

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

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 the circuit is instead over $2n$ input literals $x _ i$ and $\overline{x _ i}$.

Encode a Boolean circuit by a list of $s$ tuples $(i, j, k, t)$ where $i, j, k, t$ are integers such that $1 \le i, j, k \le s$ and $1 \le t \le 2n + 2$.

The intended interpretation of a tuple is that the gate with index $i$ has gates of indices $j$ and $j$ as children, and is of type $t$. Type $t = 1$ indicates $\text{AND}$ and $t = 2$ indicates $\text{OR}$. Then for $1 \le \ell \le n$, $t = 2 + \ell$ indicates input literal $x _ \ell$ and $t = n + 2 + \ell$ indicates input literal $\overline{x _ \ell}$.

Note that the values $j$ and $k$ are irrelevant for $t > 2$.

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} }\]

@todo.

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

In other words, 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.