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.

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

1 Answer 1


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

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

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.