Complexity of a Set of Formulas

Question

Notation: We write $|\alpha|$ to denote the length in characters of an expression $\alpha$ in propositional logic.

Consider an expression $\alpha_n$ in disjunctive normal form built from $2n$ variables where each conjunct contains $n$ variables chosen from those $2n$ original variables. All $\binom{2n}{n}$ conjuncts are included. We observe that as $n$ grows for $n \geq 2$, $|\alpha_n|$ is bounded below by $2^n$.

Here is an example over the variables $a,b,c,d$ where $n=2$: $$ \alpha_2 = (a \land b) \lor (a \land c) \lor (a \land d) \lor (b \land c) \lor (b \land d) \lor (c \land d)$$

Question: Let $\beta$ be a Boolean circuit built from the usual operations $\land$, $\lor$, and $\lnot$. Is there an equivalent set of Boolean circuits $\beta_n$ (where $\alpha_n \leftrightarrow \beta_n$ over the $2n$ inputs) such that the growth of $|\beta_n|$ is polynomially bounded, that is, there is some constant $c$ such that $|\beta_n| = O(n^c)$? Or is this impossible? Note that what I am asking is not equivalent to counting the number of true variables.

Answer 1

Yes. You can build a Boolean circuit $\beta_n$ of size $O(n \lg n)$, that is equivalent to $\alpha_n$. It works by counting the number of "true"s among the inputs, compares it to $n$, and outputs true if it is greater or equal, or false if it is less.

What's the size of this circuit? Adding up the number of "true"s can be done with $2n-1$ additions of $1+\lg n$ bit numbers, which takes $O(n \lg n)$ gates. Comparing to $n$ can be done with another $O(n)$ gates. Therefore, the total size of the circuit is $O(n \lg n)$, which is indeed polynomially bounded in $n$, as requested.