Question

The following is an elementary question about circuit complexity. It is different from the kind of thing I have seen discussed, so I would be interested in any work that has been done on this kind of question. My apologies if this is easy or well known. By a Boolean function, I mean a function from $2^n\rightarrow2^m$ where $2$ is the set with two elements $0,1$. If $f:2^n\rightarrow2^m$ and $g:2^n\rightarrow2^k$ are Boolean functions, I denote by $\langle f,g\rangle$ the function $2^n\rightarrow2^{m+k}$ whose output is the output of $f$ followed by the output of $g$. Finally, let $|f|$ be the size (i.e. number of internal nodes) of the minimal circuit computing $f$. My question is the following: Suppose $| \langle f, \langle g,h \rangle \rangle | < |f|+|g|+|h|$ . Does it follow that $|\langle x,y \rangle | < |x|+|y|$ for some pair $x,y$ chosen from $f,g,h $ ? Naively, the idea is that we can build a circuit computing $\langle f,g \rangle$ from one computing $f$ and one computing $g$, and this has size $|f|+|g|$. But if $f$ and $g$ have something "in common", perhaps we can do better. Then the question is, suppose $f,g,h$ "have something in common". Does this mean two of these functions already "have something in common"? I would also be interested in any variations on this question, for example for considering only formulas or bounded circuits.

Answer 1

Suppose there is a 2-variable function $\phi: 2^n\times 2^n \to 2^m$. Take two constant vectors $c_1,c_2\in 2^n$ and define $f(x)=\phi(x,c_1)$, $g(x)=\phi(x,c_2)$ and $h(x)=\phi(x,c_1+c_2)$. For computing any two of these, the second arguments are arbitrary constant vectors, but to compute all three one might be able to use the fact that the three second arguments have a simple relationship.

For example (does this work?), take $m=1$ and define $\phi(x,y)$ to be the inner product of $x$ and $y$ (mod 2). Then $h(x)$ can be computed very quickly as $f(x)+g(x)$ but I don't see how to do any two of $f,g,h$ faster than one at at time.