<p>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)  &lt; 2^k/k &lt; 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.    </p>

<p>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.  </p>

CC BY-SA 2.5
2011-02-24T03:58:53.670Z
No direct reason, but all known approaches (implementations of counting arguments) require that we eventually verify that the truth table of a given function has high circuit complexity. An $NE$ algorithm for this problem would define a $NP/poly$-natural property against $P/poly$ (which, according to one of Steven Rudich's papers, is unlikely). Of course, solving this problem looks unnecessary...
Ryan Williams
CC BY-SA 2.5
2011-02-24T02:59:57.807Z
2011-02-24T02:59:57.807Z
Russell Impagliazzo
<p>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.</p>

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

<p>We know that:</p>

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

<p>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$.</p>

<p>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)$.</p>

CC BY-SA 3.0
2015-07-06T05:16:44.323Z
How does the proof go that there are functions computable by circuits of size $f(n)$ but not by circuits of size $f(n) - O(1)$?
William Hoza
CC BY-SA 3.0
2011-02-24T07:59:35.753Z
2013-08-12T22:19:09.117Z
2013-08-12T22:19:09.117Z
Luca Trevisan
<p>I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.</p>

<p>Is it an interesting approach to class separation?</p>

<p>The motivation for the question is that we have to say</p>

<blockquote>
  <p>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)&lt;o(g(n))$. (and possibly something regarding the depth)</p>
</blockquote>

<p>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. </p>

<p>Is there a result in this direction?</p>

<cc.complexity-theory><circuit-complexity><lower-bounds><natural-proofs><hierarchy-theorems>
Hierarchy theorem for circuit size
AntonioFa
# Hierarchy theorem for circuit size

(Asked by: username_0 on 2011-02-24)

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)

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?

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, natural-proofs, hierarchy-theorems


---

## 2 answers

### Answer by username_3 on 2011-02-24. Score: 35 | Accepted answer

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)$.

> **Comments:**
> **username_4**: How does the proof go that there are functions computable by circuits of size $f(n)$ but not by circuits of size $f(n) - O(1)$?  

---

### Answer by username_1 on 2011-02-24. Score: 29

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.

> **Comments:**
> **username_2**: No direct reason, but all known approaches (implementations of counting arguments) require that we eventually verify that the truth table of a given function has high circuit complexity. An $NE$ algorithm for this problem would define a $NP/poly$-natural property against $P/poly$ (which, according to one of Steven Rudich's papers, is unlikely). Of course, solving this problem looks unnecessary...  

---

