Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$.
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)$.
