[Solved]: Is there an intuitive proof for the existence of hard functions?

Problem Detail: 

I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, ``For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by a circuit $C$ of size $\frac{2^n}{10n}$"

• Can someone give a more intuitive proof of this than the one presented there?

For example he proof there at one point claims with little justification that there are at most $2^{0.92^n}$ circuits of size at most $\frac{2^n}{10n}$. Why? I couldn't reproduce this ``0.92" thing!

• It seems that one even improve this theorem to higher lower bound of $\frac{2^n}{n}$. Can someone kindly help do that? How much up can one get this?

Asked By : user6818

Answered By : Yuval Filmus

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. We then compute the maximal $S$ such that $C_S < 2^{2^n}$, and conclude that there must be a function that cannot be computed by a circuit of size at most $S$. The answer is $S = O(2^n/n)$, and we usually really don't care about the hidden constant; we tend to abstract away constants in complexity theory.

The same argument shows, with very small modifications, that a random function has circuit complexity $\Omega(2^n/n)$ in expectation and with high probability.

How about an explicit function with complexity $\Omega(2^n/n)$? This is a difficult open problem. The best lower bounds we have for explicit functions are $\Omega(n^3)$ for Andreev's function (see Komargodski–Raz–Tal for the best result in this direction). I am told that obtaining anything better than $\Omega(n^3)$ would be difficult due to the natural proof barrier.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41728

3.2K people like this

 Download Related Notes/Documents