<p>It seems that nobody has added to the discussion of this question since February.</p>
<p>I'm quite sure that no better depth upper bound is known for L than <span class="math-container">$\log^2 n$</span>, in the bounded fan-in circuit model, even with no size restriction.</p>
<p>In the semi-unbounded fan-in circuit model (fan-in 2 AND and unbounded fan-in OR), log-depth is adequate to recognize not only L, but also NL, with polynomial size.  This class, known as <span class="math-container">$SAC^1$</span> is equal to the class of problems logspace-reducible to a context-free language, and it has several equivalent characterizations.</p>
<p>The &quot;natural conjecture&quot; would be that <span class="math-container">$\log^2 n$</span> is optimal ... but there's not much evidence to support that conjecture.</p>

CC BY-SA 4.0
2023-09-29T22:00:56.587Z
2023-09-29T22:00:56.587Z
Eric Allender
<p>To the best of my knowledge it is unknown that  <span class="math-container">$\mathsf{L}$</span> is subset of <span class="math-container">$\mathsf{NC}^1$</span>.</p>
<p>(Here <span class="math-container">$\mathsf{NC}^1$</span> is the class of decision problems solvable by a  family of Boolean circuits, with polynomial size, logarithmic depth , and bounded fan-in;</p>
<p><span class="math-container">$\mathsf{L}$</span> is the class of decision problems solvable  by a Turing machine restricted to use an amount of memory logarithmic in the size of the input.)</p>
<p>Let reduce restriction in the definition of <span class="math-container">$\mathsf{NC}^1$</span>: assume we allow size, say <span class="math-container">$n^{O(\log \log n)}$</span> and depth <span class="math-container">$O(\log n \log \log n)$</span>. Can we solve any problem in <span class="math-container">$\mathsf{L}$</span> by such circuits?</p>
<p>Are there any natural conjectures about it?</p>

CC BY-SA 4.0
2023-02-08T18:41:13.360Z
$L\subseteq NC^2$ is known and so $n^{O(1)}$ size and depth $O(\log^2n)$ suffices. The OP is asking for tradeoffs between size and depth.
Turbo
CC BY-SA 4.0
2023-02-08T19:03:56.193Z
$NC^2 \subseteq quasiNC^1$ (log-depth, quasi-poly size), and I think this is the best known size upper bound on log-depth circuits to compute $NC^2$ problems. If you ask about size upper bound on log-depth circuits to compute logspace, I don't know if anything better is known (but I kinda doubt it...).
Joshua Grochow
CC BY-SA 4.0
2023-02-08T19:35:25.900Z
@JoshuaGrochow Could you please give a reference about quasi$NC^{1}$? Your definition confuses me:  if depth is $O(\log n)$ and fan-in is bounded then output depends on poly(n) vertices, isn't it?
Alexey Milovanov
CC BY-SA 4.0
2023-02-08T19:42:09.277Z
@AlexeyMilovanov: Yes, but...vertices of what? There are only n input bits. I'll see if I can dig up a ref about quasiNC^1
Joshua Grochow
CC BY-SA 4.0
2023-02-08T19:48:42.390Z
Couldn't easily find a ref, but the idea is: try to turn your NC^2 circuit into a formula (where the underlying DAG of the circuit is a tree), as NC^1 = poly-size formulas. If you do that by duplicating various subcircuits, you increase the size by a factor that is roughly $2^{depth}$. In this case, that's $2^{O(\log^2 n)} = n^{O(\log n)}$.
Joshua Grochow
CC BY-SA 4.0
2023-02-08T22:13:38.940Z
@JoshuaGrochow This will have depth $O((\log n)^2)$ though, not $O(\log n)$. Indeed, $O(\log n)$ depth bounded fan-in circuits have automatically polynomial size. The correct definition of quasiNC^1 should have depth logarithmic in circuit size rather than in $n$ (so the inclusion of NC^2 in quasiNC^1 is trivial: the $O((\log n)^2)$ depth polynomial-size circuit is a quasiNC^1 circuit as is).
Emil Jeřábek
CC BY-SA 4.0
2023-02-08T22:36:12.710Z
@Emil: Oh, I guess by "quasiNC^1" I was thinking a formula with bounded fan-in gates, unbounded depth, quasi-poly size. (Since NC^1 = poly-size formulas of unbounded depth.) But, right, that doesn't give you a quasi-poly size log-depth NC circuit, as those don't exist (oops!).
Joshua Grochow
CC BY-SA 4.0
2023-02-09T07:28:35.467Z
By the way, in the question, depth $O(\log n\log\log n)$ by itself implies size $n^{O(\log\log n)}$, making the $n^{O(\log n)}$ bound redundant.
Emil Jeřábek
CC BY-SA 4.0
2023-02-09T12:29:17.453Z
@EmilJeřábek fixed it, thank you
Alexey Milovanov
<logspace><circuit-depth>
What circuit depth is enough to compute a log-space complete problem?
Alexey Milovanov
# What circuit depth is enough to compute a log-space complete problem?

(Asked by: username_0 on 2023-02-08)

To the best of my knowledge it is unknown that $\mathsf{L}$ is subset of $\mathsf{NC}^1$.

(Here $\mathsf{NC}^1$ is the class of decision problems solvable by a family of Boolean circuits, with polynomial size, logarithmic depth , and bounded fan-in;

$\mathsf{L}$ is the class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input.)

Let reduce restriction in the definition of $\mathsf{NC}^1$: assume we allow size, say $n^{O(\log \log n)}$ and depth $O(\log n \log \log n)$. Can we solve any problem in $\mathsf{L}$ by such circuits?

Are there any natural conjectures about it?

**Tags:** logspace, circuit-depth
> **Comments:**
> **username_1**: $L\subseteq NC^2$ is known and so $n^{O(1)}$ size and depth $O(\log^2n)$ suffices. The OP is asking for tradeoffs between size and depth.  
> **username_2**: $NC^2 \subseteq quasiNC^1$ (log-depth, quasi-poly size), and I think this is the best known size upper bound on log-depth circuits to compute $NC^2$ problems. If you ask about size upper bound on log-depth circuits to compute logspace, I don't know if anything better is known (but I kinda doubt it...).  
> **username_0**: @JoshuaGrochow Could you please give a reference about quasi$NC^{1}$? Your definition confuses me:  if depth is $O(\log n)$ and fan-in is bounded then output depends on poly(n) vertices, isn't it?  
> **username_2**: @AlexeyMilovanov: Yes, but...vertices of what? There are only n input bits. I'll see if I can dig up a ref about quasiNC^1  
> **username_2**: Couldn't easily find a ref, but the idea is: try to turn your NC^2 circuit into a formula (where the underlying DAG of the circuit is a tree), as NC^1 = poly-size formulas. If you do that by duplicating various subcircuits, you increase the size by a factor that is roughly $2^{depth}$. In this case, that's $2^{O(\log^2 n)} = n^{O(\log n)}$.  
> **username_3**: @JoshuaGrochow This will have depth $O((\log n)^2)$ though, not $O(\log n)$. Indeed, $O(\log n)$ depth bounded fan-in circuits have automatically polynomial size. The correct definition of quasiNC^1 should have depth logarithmic in circuit size rather than in $n$ (so the inclusion of NC^2 in quasiNC^1 is trivial: the $O((\log n)^2)$ depth polynomial-size circuit is a quasiNC^1 circuit as is).  
> **username_2**: @Emil: Oh, I guess by "quasiNC^1" I was thinking a formula with bounded fan-in gates, unbounded depth, quasi-poly size. (Since NC^1 = poly-size formulas of unbounded depth.) But, right, that doesn't give you a quasi-poly size log-depth NC circuit, as those don't exist (oops!).  
> **username_3**: By the way, in the question, depth $O(\log n\log\log n)$ by itself implies size $n^{O(\log\log n)}$, making the $n^{O(\log n)}$ bound redundant.  
> **username_0**: @EmilJeřábek fixed it, thank you  

---

## 1 answers

### Answer by username_4 on 2023-09-29. Score: 7 | Accepted answer

It seems that nobody has added to the discussion of this question since February.

I'm quite sure that no better depth upper bound is known for L than $\log^2 n$, in the bounded fan-in circuit model, even with no size restriction.

In the semi-unbounded fan-in circuit model (fan-in 2 AND and unbounded fan-in OR), log-depth is adequate to recognize not only L, but also NL, with polynomial size. This class, known as $SAC^1$ is equal to the class of problems logspace-reducible to a context-free language, and it has several equivalent characterizations.

The "natural conjecture" would be that $\log^2 n$ is optimal ... but there's not much evidence to support that conjecture.


---

