2
$\begingroup$

Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show that $L(f_1 \oplus \cdots \oplus f_n) \geq \frac{1}{2}\sum_{i = 1}^n L(f_i)$ (where we use the De Morgan basis)? Here, we mean $L(f)$ is the size of the boolean function $f$ which is the minimum number of $\wedge, \vee, \neg$ input gates across all boolean circuits that compute $f$.

It makes intuitive sense that you need at least half the bits going into the gates to compute the overall parity, but I'm not exactly sure how to rigorously show this. Also, I suppose the functions should be non-constant or else this lower bound may not hold. I'm not sure we can know what the circuit for $f_1 \oplus \cdots \oplus f_n$ looks like, but perhaps there are some theorems that give intuition about the size of such a circuit. Any help is appreciated!

$\endgroup$
0

1 Answer 1

0
$\begingroup$

This is false, various construction for computing simultaneously the same function on disjoint sets of variables are discussed in this cstheory.stackoverflow question.

$\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.