Functions with small support have small circuits 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 &quot;support&quot; 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.
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$.