1
$\begingroup$

I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:

Show that if a function $f\colon \{0,1\}^n→\{0,1\}$ has a support of size $k$, then it can be decided by a circuit of size $O(nk)$.

I understand that for any binary functions of this sort, the maximal size of the circuit is $O(n2^n)$, and I have a feeling that this could be useful for proving the statement, but I am not exactly sure where to proceed from there. Furthermore, I also understand that the "support" referred to in this question is actually the language defined by the function, but again, this leads me nowhere.

Any help on this would be much appreciated.

$\endgroup$
2
  • $\begingroup$ Do you know the definition of support? Without knowing the definition you will be unable to solve this question. $\endgroup$ – Yuval Filmus Nov 26 '20 at 14:34
  • $\begingroup$ By the way, every function can be computed using a circuit of size $O(2^n/n)$. $\endgroup$ – Yuval Filmus Nov 26 '20 at 14:34
0
$\begingroup$

Consider the AND function: $$ x_1 \land \cdots \land x_n. $$ Its support size is $1$, and its circuit complexity is $O(n)$. By negating inputs, you can get a circuit for any function whose support size is $1$. By ORing together $k$ such functions, you can get a circuit of size $O(kn)$ for any function whose support size is $k$.

$\endgroup$
1
  • $\begingroup$ Thank you! I realized this eventually after some thought, but your explanation makes a lot more sense! $\endgroup$ – haggisman18 Nov 26 '20 at 14:49

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.