3
$\begingroup$

Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\} $ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a hint.

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Apr 4 '17 at 17:33
3
$\begingroup$

Hint: Estimate from above the number of circuits with $2^n/2n$ gates, and compare it to the number of functions.

$\endgroup$
3
$\begingroup$

We need counting argument here. First thing is, there are $2^{2^{n}}$ many boolean functions, second thing is to count the number of boolean circuits for $k$ size boolean circuit. There are $2^{k^2} \times 3^{k}$ many boolean circuits of size $k$ (use adjacency matrix ). In your case value of $k =\frac{ 2^n}{2n}$, now you can easily check that

$$2^{2^{n}} > 2^{k^2} \times 3^{k} $$

So it means there are more number of functions than the total number of boolean circuits. There has to be at least one function that can not be computed by $k$ size circuit ( pigeonhole principle ). One thing to note here that I have proved the existence of such type of boolean circuit but to come up with such type of boolean circuit is quite hard.

$\endgroup$
  • 1
    $\begingroup$ Parity can be computed with a linear size circuit. $\endgroup$ – Yuval Filmus Apr 4 '17 at 18:55
  • 1
    $\begingroup$ @Yuval Filmus yes I have edited my answer $\endgroup$ – aaag Apr 23 '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.