Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top