Prove that for some size of circuit there exists function which requires some number of gates

38 Views Asked by At

Prove that for every function $s(n)$ such that $n≤s(n)≤\frac{2^n}{100n}$ there exists a Boolean function $f:{0,1}^n→{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)$

Could anyone give me some help ?