Circuits

Definition An \(n\)-ary boolean function is a function \(f:\{0,1\}^n\to \{0,1\}\).

Proposition For every boolean function \(f\) there is a propositional formula \(\varphi\) such that the function defined by \(\varphi\) is equal to \(f\).

Definition The size of a circuit is defined as the amount of and-, not-, and or-gates.

Definition Suppose that \(\{C_n\}_{n\in \mathbb{N}}\) is a family of circuits such that for every \(n\), \(C_n\) computes a boolean function of \(n\) inputs. A family computes a language \(L\) if for all \(x\in \{0,1\}^n\) we have

\[x\in L \iff C_n(x) =1\]

\(\text{SIZE}(s(n))\) denotes the class of languages \(L\) that are computed by a circuit family such that the size of \(C_n\) is bounded by \(s(n)\).

Proposition Any language is in \(\text{SIZE}(O(2^n))\).

Proposition There are languages with subsexponential circuit size: For any subsexponential s there is a langue \(L\notin \text{SIZE}(s(n))\).

Proof We need to count the amount of circuits with size \(s\). There are \(s\) internal gates and \(n\) input gates. For every gate we give one of the three types and where the two inputs come from. This costs no more than

\[s\cdot (2\log(n+s)+3)\leq s\cdot (2\log s+5)\]

bits. The total number of circuits of size s is bounded by \(2^{s(2\log s +5)}\), but there are \(2^{2^n}\) boolean functions. By counting we see that they cannot all be bounded by \(s\).. End Proof

Definition Let \(\mathcal{C}\) be a complexity class and \(\mathcal{F}\) a class of advice functions \(s:\mathbb{N}\to \{0,1\}^*\). Then we define

\[\mathcal{C}/\mathcal{F}:=\{\{x\mid \langle x,s(|x|)\rangle \in B \}\mid B\in\mathcal{C}, s\in \mathcal{F}\}.\]

Theorem P/poly = SIZE\((n^{O(1)})\).

Proof The direction from right to left follows from the fact that you can compute a polynomial sized circuit in polynomial time. For \(A\) of size \((n^{O(1)})\) we have

\[x\in A \iff \langle x,C_{|x|}\rangle \in B\]

, hence \(A\in\)P/poly. For the converse we need to show that a computation of a polynomial time Turing machine with fixed sized inputs can be converted into a polynomial size circuit. End Proof

Theorem BPP\(\subseteq\)SIZE\((n^{O(1)})\).