1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Well there exists $2^{2^n}$ possible $f$ functions. How many circuits can exist with size at most $s(n)$? $\endgroup$ – Bakuriu Mar 14 '16 at 11:07
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – user54001 Apr 29 '17 at 13:12
  • $\begingroup$ 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$.) $\endgroup$ – Yuval Filmus Apr 29 '17 at 13:15
  • $\begingroup$ 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. $\endgroup$ – user54001 Apr 30 '17 at 11:51
  • $\begingroup$ Most probably they saw this part in class. By the way, a gap of 10 is probably not good enough. $\endgroup$ – Yuval Filmus Apr 30 '17 at 12:46

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.