# A function computable using a circuit of size $10s$ but not of size $s$

I'm studying Computational Complexity and I have stumbled upon the following question which I have no idea how to even start proving. I would appreciate any help.

Prove that for every function $s(n)$ such that $n \le s(n) \le \frac{2^n}{100n}$ there exists a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$ such that $f$ doesn't have a Boolean circuit of size $s(n)$ that computes it but has a Boolean circuit of size $10s(n)$.

• Well there exists $2^{2^n}$ possible $f$ functions. How many circuits can exist with size at most $s(n)$? Mar 14, 2016 at 11:07

One possible approach is as follows. A counting argument shows that there are function on $n$ bits that require circuits of size $\Omega(2^n/n)$, and on the other hand a non-trivial construction that you probably saw in class shows that every function on $n$ bits can be computed using a circuit of size $O(2^n/n)$. This takes care of the case $s(n) = 2^n/{100n}$.
For general values of $s(n)$, you can use functions depending on $m \leq n$ variables, making sure that the resulting lower bound $\Omega(2^m/m)$ and upper bound $O(2^m/m)$ fit snugly around $s(n)$.
• Could you be more precisely about your solution ? I can't see how you show that there exists that is computable by circuit of size $s(n)$, but not $10s(n)$.
• Yes, there are a few details missing here. It is good to work them out on your own. In particular, in order to get $s(n)$ vs. $10s(n)$ you need to start with a somewhat more precise base point, determining constants $A,B$ such that there is a function computable using circuits of size $A(2^n/n)$ but not of size $B(2^n/n)$. If $A/B$ is small enough, then you will be able to get $s(n)$ vs. $10s(n)$. (Otherwise you will get some constant different from $10$.) Apr 29, 2017 at 13:15
• If I found function such that $A=\frac{1}{10}$ and $B=\frac{1}{100}$ I would got a result. I know it. (There are only example constants). Your hint was about reparaphrase thesis of exrcise, nothing more. It doesn't help because findind such functions can be difficult, I can't see how to do it.