1
$\begingroup$

Every function $f\colon \{ 0, 1 \}^n \to \{ 0, 1 \}$ can be computed by a circuit over the standard unbounded fan-in basis $\mathcal{B}_1 = \{ \neg, (\vee^n)_{n \in \mathbb{N}}, (\wedge^n)_{n \in \mathbb{N}} \}$ of depth $3$ and size $\mathcal{O}(2^n)$ via the disjunctive or conjunctive normal form. Now, we can transform each circuit over $\mathcal{B}_1$ into a circuit over the standard bounded fan-in basis $\mathcal{B}_0 = \{ \neg, \vee, \wedge \}$ by substituting a gate of fan-in $k$ by a circuit of depth $\mathcal{O}(\log k)$ and size $\mathcal{O}(k)$ and, since each gate of the original circuit has a fan-in smaller than $\mathcal{O}(2^n)$, we get a circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(2^{2n})$. How does http://www.cs.umd.edu/~jkatz/complexity/f05/lecture4.pdf obtain a size bounded by $\mathcal{O}(n \cdot 2^n)$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Every function can be computed by a CNF (or a DNF). A CNF is the conjunction of up to $2^n$ clauses. Each clause involves up to $n$ variables. You can express each clause using a circuit of size $O(n)$, and the entire CNF using a circuit of size $O(n 2^n)$. In fact, this constructs a formula of size $O(n2^n)$.

The conversion from $\mathcal{B}_1$ to $\mathcal{B}_0$ doesn't increase the number of leaves in the circuit, and only increases the number of wires by a constant factor. It could increase the number of gates by an unbounded amount: for example, a fan-in $k$ AND gates translates to $k-1$ fan-in $2$ AND gates.

Lupanov improved the above bound to $O(2^n/n)$, which is tight due to a counting argument; see for example lecture notes of Jayalal Sarma. In the case of formulas, the tight bound is $O(2^n/\log n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.