<p>No, <span class="math-container">$\mathrm{AC}^0[2^{n^\delta}]$</span> is not included in NC; it is not even included in <span class="math-container">$\mathrm{SIZE}[2^{n^\epsilon}]$</span> for <span class="math-container">$\epsilon&lt;\delta$</span>. Indeed, any Boolean function on <span class="math-container">$n^\delta$</span> inputs, padded to input size <span class="math-container">$n$</span> with dummy variables, has depth-2 circuits of size <span class="math-container">$2^{n^\delta}$</span>, but the vast majority of such functions require circuit size <span class="math-container">$\Omega(2^{n^\delta}/n^\delta)$</span>.</p>
<p>By the way, the opposite inclusion can be improved: not only does <span class="math-container">$\mathrm{AC}^0[2^{n^\epsilon}]$</span> contain <span class="math-container">$\mathrm{NC}^1$</span> without the <span class="math-container">$\epsilon\log n$</span> depth restriction, we have, in fact,
<span class="math-container">$$\mathrm{NL/poly}\subseteq\bigcap_{\epsilon&gt;0}\mathrm{AC}^0[2^{n^\epsilon}].$$</span>
This is a form of Nepomnjaščij’s theorem.</p>

CC BY-SA 4.0
2022-03-09T07:45:10.200Z
2022-03-09T08:19:11.830Z
2022-03-09T08:19:11.830Z
Emil Jeřábek
<p>My question is about the possibility of trading size for depth in circuits.</p>
<p>Under what conditions is it true (or, plausible) that <span class="math-container">$AC^0[2^{n^\delta}] \subseteq NC^i$</span> for some constants <span class="math-container">$\delta &lt; 1, i&gt;0$</span>?</p>
<p>Or, is there anything known at all?</p>
<p>I can see that <span class="math-container">$NC^1$</span> circuits of depth <span class="math-container">$\epsilon\mathrm{log}(n)$</span> (for <span class="math-container">$\epsilon&lt;1$</span>) are contained in <span class="math-container">$AC^0[2^{n^\epsilon}]$</span>. My question goes in the other direction.</p>

<circuit-complexity><dc.parallel-comp><circuit-depth><bounded-depth>
$AC^0$[subexp] vs. NC
zfkmz
# $AC^0$[subexp] vs. NC

(Asked by: username_0 on 2022-03-09)

My question is about the possibility of trading size for depth in circuits.

Under what conditions is it true (or, plausible) that $AC^0[2^{n^\delta}] \subseteq NC^i$ for some constants $\delta < 1, i>0$?

Or, is there anything known at all?

I can see that $NC^1$ circuits of depth $\epsilon\mathrm{log}(n)$ (for $\epsilon<1$) are contained in $AC^0[2^{n^\epsilon}]$. My question goes in the other direction.

**Tags:** circuit-complexity, dc.parallel-comp, circuit-depth, bounded-depth

---

## 1 answers

### Answer by username_1 on 2022-03-09. Score: 10 | Accepted answer

No, $\mathrm{AC}^0[2^{n^\delta}]$ is not included in NC; it is not even included in $\mathrm{SIZE}[2^{n^\epsilon}]$ for $\epsilon<\delta$. Indeed, any Boolean function on $n^\delta$ inputs, padded to input size $n$ with dummy variables, has depth-2 circuits of size $2^{n^\delta}$, but the vast majority of such functions require circuit size $\Omega(2^{n^\delta}/n^\delta)$.

By the way, the opposite inclusion can be improved: not only does $\mathrm{AC}^0[2^{n^\epsilon}]$ contain $\mathrm{NC}^1$ without the $\epsilon\log n$ depth restriction, we have, in fact,
$$\mathrm{NL/poly}\subseteq\bigcap\_{\epsilon>0}\mathrm{AC}^0[2^{n^\epsilon}].$$
This is a form of Nepomnjaščij’s theorem.


---

