3
$\begingroup$

There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits.

A classic result in circuit complexity is that, if you count the total number of gates needed to implement $f$, most $f$s take $\Theta(2^n/n)$ 2-to-1 boolean gates. I'm interested in a slightly different metric, where you can use as many XOR gates as you want but you don't count them (ditto for NOT gates, which are just a XOR with one input constant). So your circuit could have $n$ AND gates plus $2^n$ XOR gates, and I'd call that a circuit of non-XOR-size $n$.

I've figured out that it's possible to implement any $n$-input function $f$ using at most $2^{n/2+1}$ gates that aren't XOR or NOT. The strategy works by using $2^{n/2}$ AND gates (with XOR gates interspersed) to prepare a set of $2^{n/2}$ indicator bits that can be XOR'd together to make any function of $n/2$ bits. I then pretend the top $n/2$ bits of the input index register are "choosing" the sub-function to apply with the bottom $n/2$ bits, and use my indicator bits to prepare the $2^{n/2}$ possible sub-function outputs. I then use $2^{n/2}$ AND gates to mux out the desired sub-function output (selected by the top $n/2$ bits of the input index register).

I'm interested in knowing is it possible to do better than $2^{n/2+1}$ AND gates, or is that asymptotically optimal.

$\endgroup$
3
$\begingroup$

By counting circuits, $2^{n/2 + 1}$ appears to be close to asymptotically optimal.

Let $C_{n,k}$ be the number of distinct circuits with $n$ bits and $k$ AND gates.

We lower bound $C_{n,k}$ by noting that we need to choose $k$ such that there is at least as many possible circuits as possible functions, i.e. $2^{2^n} \leq C_{n,k}$.

We upper bound $C_{n,k}$ by noting that every AND gate takes as input a bit which may have had each initial input and each output of a previous AND gate and possibly the constant 1 XOR'd into it. For the first AND gate there are $n + 1$ bits that may or may not be xored into each input of rht AND gate. For the second AND gate there are $n + 2$ bits, for the third $n+3$, and so forth. Then there's $n+k+1$ choices for what to xor into our output bit. Thus $C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$.

Now we know $2^{2^n} \leq C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$. By omitting the $C_{n,k}$ in the center we get an inequality in terms of $k$ and $n$ that we can use to bound $k$ in terms of $n$ as follows:

$$\begin{align} 2^{2^n} &\leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1} \\ &= 2^{n+k+1} \prod_{i=1}^k 4^{n+i} \\ &= 2^{n+k+1} 4^{\sum_{i=1}^k n+i} \\ &= 2^{n+k+1} 4^{kn + k(k+1)/2} \\ &= 2^{2kn + k^2 + 2k + n + 1} \end{align}$$

Now we start manipulating both sides:

$$\begin{align} 2^{2^n} &\leq 2^{2kn + k^2 + 2k + n + 1} \\ 2^n &\leq 2kn + k^2 + 2k + n + 1 \\ 0 &\leq k^2 + k(2n + 2) + (n + 1 - 2^n) \end{align}$$

Finally, find the quadratic roots where the inequality switches, and focus down to the asymptotically dominant term of the positive root:

$$\begin{align} k &= \frac{-2n -2 \pm \sqrt{(2n+2)^2 + 4 \cdot (2^n - n - 1)}}{2} \\ &= -n - 1 \pm \sqrt{n^2 + 2n + 1 + 2^n - n - 1} \\ &= -n - 1 \pm \sqrt{n^2 + n + 2^n} \\ &\in \Omega \left(-n -\frac{1}{2} + \sqrt{n^2 + n + 2^n} \right) \\ &= \Omega \left(\sqrt{2^n} \right) \\ \end{align}$$

So it appears that $k$ must be asymptotically at least $\Omega(\sqrt{2^n})$ in order for there to be enough circuits to cover all of the possible functions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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