Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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