51 Formulas

The size of a formula is its number of propositional variable occurrences.

Proposition (Formula unfolding)

If $L\subseteq \{0,1{\}}^n$ is computed by a circuit $C$ of depth $d$, then it is computed by a formula of size $<2^{d+1}$

Proof

For a node $v$ of $C$, define the formula $F(v)$ by induction on depth of $v$:

• $F(x_i)$ is just the formula $x_i$ (of size $1<2=2^1$)
• If $v$ of depth $e$ is labelled $\neg$ with incoming edge from $u$ (of depth $<e$), then $F(v):=\neg F(u)$ (of size $<2^e$) by IH and so $<2^{e+1}$
• If $v$ of depth $e$ is labelled $\star \in \{\wedge ,\vee \}$ with incoming edges from $u_0,u_1$ (of depth $<e$) then $F(v):=(F(u_0)\star F(u_1))$ (of size $<2^e+2^e$ by IH and so $<2^{e+1}$ Now $F(s)$ is a formula computing $L$ of size $<2^d$.

We say that a language $L\subseteq \{0,1{\}}^{\star }$ is computed by a circuit family $\{C_n{\}}_{n=1}^{\infty }$ if, for each $n\in \mathbb{N}$, $C_n$ is an $n$-input circuit computing $L\cap \{0,1{\}}^n$.

Definition (Size and Depth)

Let $f:\mathbb{N}\to \mathbb{N}$

• $\mathbf{SIZE}(f(n))$ is the set of languages $L\subseteq \{0,1{\}}^{\star }$ computed by circuits of size $\le f(n)$
• $\mathbf{DEPTH}(f(n))$ is the set of languages $L\subseteq \{0,1{\}}^{\star }$ computed by circuits of depth $\le f(n)$

Definition

The class P/poly is the class of languages computed by polynomial size circuit families i.e.,

$$\mathbf{P}/poly:=\bigcup _{c=1}^{\infty }\mathbf{SIZE}(n^c)$$