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 saythere 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?
Hierarchy theorem for circuit size
cc.complexity theory;circuit complexity;lower bounds;natural proofs;hierarchy theorems
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:there is a function $g$ that requires circuit complexity at least $2^n/O(n)$, and, in particular, circuit complexity more than $f(n)$.the function $z$ such that $z(x)=0$ for every input $x$ is computable by a constant-size circuit.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)$.