Hierarchy theorem for circuit size

Question

I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.

Is it an interesting approach to class separation?

The motivation for the question is that we have to say

there is some function that cannot be computed by size $f(n)$ circuits and can be computed by a size $g(n)$ circuit where $f(n)<o(g(n))$. (and possibly something regarding the depth)

so, if $f(m)g(n) \leq n^{O(1)}$, the property seem to be unnatural (it violates the largeness condition). Clearly we can't use diagonalization, because we aren't in a uniform setting.

Is there a result in this direction?

Answer 1

In fact it is possible to show that, for every $f$ sufficiently small (less than $2^n/n$), there are functions computable by circuits of size $f(n)$ but not by circuits of size $f(n)-O(1)$, or even $f(n)-1$, depending on the type of gates that you allow.

Here is a simple argument that shows that there are functions computable in size $f(n)$ but not size$ f(n)-O(n)$.

We know that:

1. there is a function $g$ that requires circuit complexity at least $2^n/O(n)$, and, in particular, circuit complexity more than $f(n)$.
2. the function $z$ such that $z(x)=0$ for every input $x$ is computable by a constant-size circuit.
3. if two functions $g_1$ and $g_2$ differ only in one input, then their circuit complexity differs by at most $O(n)$

Suppose that $g$ is nonzero on $N$ inputs. Call such inputs $x_1,\ldots,x_N$. We can consider, for each $i$, the function $g_i(x)$ which is the indicator function of the set $\{ x_1,\ldots,x_i \}$; thus $g_0=0$ and $g_N=g$.

Clearly there is some $i$ such that $g_{i+1}$ has circuit complexity more than $f(n)$ and $g_i$ has circuit complexity less than $f(n)$. But then $g_{i}$ has circuit complexity less than $f(n)$ but more than $f(n) - O(n)$.

Answer 2

This result can be proved using a simple counting argument. Consider a random function applied to the first $k$ bits of the input. This function almost certainly has circuit complexity $(1+o(1))(2^k/k)$ by Riordan and Shannon's counting argument, and matching upper bounds. Thus, picking $k$ so that $2g(n) < 2^k/k < f(n)/2$ we can distinguish size $g(n)$ from size $f(n)$. Note that the functions in question won't necessarily even be computable, but we can put them in the exponential time hierarchy by standard techniques (as long as we can compute the right value of $k$). We of course cannot prove any bound greater than $2^n/n$, because that is the worst-case circuit complexity of any function.

Natural proofs do not apply for this type of argument, because the property in question is ``not having a small circuit'', which is not easily computable from the truth table of the function (presumably). It is not clear how low in complexity classes this type of counting can go. Is there any reason why we can't use a counting argument to prove lower bounds for $NE$? Not that I know of.