<p>1) Realize that nondeterminism is a red herring here. You could have used alternation or circuits that have gates that solve the halting problem. It boils down to a simple counting argument that once you fix the model, you can only compute $2^k$ functions that have a $k$ bit description.</p>

<p>2) For uniform classes like P this is more challenging, as there is no clear definition of "average function in P" and the counting arguments no longer work so cleanly. It's consistent with current knowledge that everything in P can be solved in nondeterministic linear time.</p>

CC BY-SA 4.0
2018-07-07T12:15:25.093Z
Do you have any pointer for this last assertion about P and NTIME(n)?
C.P.
CC BY-SA 4.0
2018-07-07T12:27:58.193Z
I meant that it is an open problem whether P is contained in NTIME(n). The problem is discussed in a Ravi Kannan Paper (https://doi.org/10.1145/800061.808764).
Lance Fortnow
CC BY-SA 4.0
2018-07-07T15:23:57.247Z
@LanceFortnow Do we know $P\not\subseteq NTIME(n^\alpha)$ at any $\alpha\in(0,1)$? What is the smallest $\alpha$ that this is true?
Turbo
CC BY-SA 4.0
2018-07-07T16:25:59.623Z
I believe the parity function cannot be computed in NTIME($n^\alpha$) time for any $\alpha<1$. Otherwise you'd have $2^{o(n)}$ size depth-2 circuits for parity which cannot happen.
Lance Fortnow
CC BY-SA 4.0
2018-07-07T22:42:27.400Z
@LanceFortnow It seems then $P\not\subseteq \exists(\log n)TIME[polylog(n)]$?
Turbo
CC BY-SA 4.0
2018-07-07T23:20:07.247Z
Does it seem then..?
Turbo
CC BY-SA 4.0
2018-07-07T11:53:35.373Z
2018-07-07T11:53:35.373Z
Lance Fortnow
<p><a href="http://www2.cs.cas.cz/~savicky/papers/fcntfinal.ps" rel="noreferrer">Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size)</a> prove the following result.</p>

<blockquote>
  <p><strong>Theorem[SW98]:</strong> For every constant $k&gt;1$, almost all boolean functions with formula
  complexity at most $n^k$ have circuit complexity at least $n^k/k$.</p>
</blockquote>

<p>The proof consists of deriving a lower bound on $B(n,n^k)$, the number of boolean functions on $n$ inputs computed by formulas of size $n^k$. By comparing $B(n,n^k)$ to the number of circuits of size $C = n^k/k$, which is at most $C^{C}e^{C+4n}$, it can be realized that for large $n$, $C^{C}e^{C+4n} &lt;&lt; B(n,n^k)$, and the result follows.</p>

<p>It looks to me that the result could be strengthened by noting that the number of nondeterministic circuits of size $n^k$ with $m$ nondeterministic inputs is not much larger than the number of deterministic circuits of size $n^k$ (for $m$ not too large, say $m=n$). Hence, I think the following corollary holds:</p>

<blockquote>
  <p><strong>Corollary:</strong> For every constant $k&gt;1$, almost all boolean functions with formula
  complexity at most $n^k$ have nondeterministic circuit complexity at least $n^k/k$ (for nondeterministic circuits with $n$ nondeterministic inputs).</p>
</blockquote>

<p>(Recall that a nondeterministic circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "nondeterministic" inputs $y=(y_1,\dots,y_m)$. A nondeterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$). </p>

<p>Obviously, the lower bound on $B(n,n^k)$ is also a lower bound on the number of boolean functions on $n$ inputs computed by circuits of size $n^k$, hence "formula complexity at most $n^k$" can be replaced by "circuit complexity at most $n^k$" in the corollary. The corollary can also be stated as: for functions with polynomial circuit complexity, switching to nondeterministic circuits cannot, on average, decrease the complexity by more than a constant factor.</p>

<blockquote>
  <p><strong>Questions:</strong></p>
  
  <p>(1) Are there any interesting implications/consequences of the corollary above?</p>
  
  <p>(2) Are there any other results in the same direction? For example, what is known about the following proposition? For problems in P, switching from TMs to NTMs cannot, on average, decrease the complexity by more than a constant factor. </p>
</blockquote>

<p>(Gil Kalai also has a <a href="https://cstheory.stackexchange.com/questions/32233/to-what-extent-computational-ability-for-hard-tasks-helps-in-solving-easy-tasks"> question</a>  somewhat related to this one.)</p>

<cc.complexity-theory><circuit-complexity><nondeterminism>
Nondeterminism is on average useless for circuits?
Gustav Nordh
# Nondeterminism is on average useless for circuits?

(Asked by: username_0 on 2018-07-07)

[Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size)](http://www2.cs.cas.cz/~savicky/papers/fcntfinal.ps) prove the following result.

> **Theorem[SW98]:** For every constant $k>1$, almost all boolean functions with formula
> complexity at most $n^k$ have circuit complexity at least $n^k/k$.

The proof consists of deriving a lower bound on $B(n,n^k)$, the number of boolean functions on $n$ inputs computed by formulas of size $n^k$. By comparing $B(n,n^k)$ to the number of circuits of size $C = n^k/k$, which is at most $C^{C}e^{C+4n}$, it can be realized that for large $n$, $C^{C}e^{C+4n} << B(n,n^k)$, and the result follows.

It looks to me that the result could be strengthened by noting that the number of nondeterministic circuits of size $n^k$ with $m$ nondeterministic inputs is not much larger than the number of deterministic circuits of size $n^k$ (for $m$ not too large, say $m=n$). Hence, I think the following corollary holds:

> **Corollary:** For every constant $k>1$, almost all boolean functions with formula
> complexity at most $n^k$ have nondeterministic circuit complexity at least $n^k/k$ (for nondeterministic circuits with $n$ nondeterministic inputs).

(Recall that a nondeterministic circuit has, in addition to the ordinary inputs $x = (x\_1,\dots,x\_n)$, a set of "nondeterministic" inputs $y=(y\_1,\dots,y\_m)$. A nondeterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$).

Obviously, the lower bound on $B(n,n^k)$ is also a lower bound on the number of boolean functions on $n$ inputs computed by circuits of size $n^k$, hence "formula complexity at most $n^k$" can be replaced by "circuit complexity at most $n^k$" in the corollary. The corollary can also be stated as: for functions with polynomial circuit complexity, switching to nondeterministic circuits cannot, on average, decrease the complexity by more than a constant factor.

> **Questions:**
>
> (1) Are there any interesting implications/consequences of the corollary above?
>
> (2) Are there any other results in the same direction? For example, what is known about the following proposition? For problems in P, switching from TMs to NTMs cannot, on average, decrease the complexity by more than a constant factor.

(Gil Kalai also has a  [question](https://cstheory.stackexchange.com/questions/32233/to-what-extent-computational-ability-for-hard-tasks-helps-in-solving-easy-tasks) somewhat related to this one.)

**Tags:** cc.complexity-theory, circuit-complexity, nondeterminism


---

## 1 answers

### Answer by username_1 on 2018-07-07. Score: 8 | Accepted answer

1) Realize that nondeterminism is a red herring here. You could have used alternation or circuits that have gates that solve the halting problem. It boils down to a simple counting argument that once you fix the model, you can only compute $2^k$ functions that have a $k$ bit description.

2) For uniform classes like P this is more challenging, as there is no clear definition of "average function in P" and the counting arguments no longer work so cleanly. It's consistent with current knowledge that everything in P can be solved in nondeterministic linear time.

> **Comments:**
> **username_2**: Do you have any pointer for this last assertion about P and NTIME(n)?  
> **username_1**: I meant that it is an open problem whether P is contained in NTIME(n). The problem is discussed in a Ravi Kannan Paper (https://doi.org/10.1145/800061.808764).  
> **username_3**: @LanceFortnow Do we know $P\not\subseteq NTIME(n^\alpha)$ at any $\alpha\in(0,1)$? What is the smallest $\alpha$ that this is true?  
> **username_1**: I believe the parity function cannot be computed in NTIME($n^\alpha$) time for any $\alpha<1$. Otherwise you'd have $2^{o(n)}$ size depth-2 circuits for parity which cannot happen.  
> **username_3**: @LanceFortnow It seems then $P\not\subseteq \exists(\log n)TIME[polylog(n)]$?  
> **username_3**: Does it seem then..?  

---

