<p>It is known that <span class="math-container">$\mathsf{NL} \subseteq \mathsf{AC}^1$</span> (because <span class="math-container">$\mathsf{NL}$</span>-complete  problem <strong>PATH</strong> belongs to <span class="math-container">$\mathsf{AC}^1$</span>).</p>
<p>Are there problems in <span class="math-container">$\mathsf{AC}^1$</span> that are unknown to be in <span class="math-container">$\mathsf{NL}?$</span></p>
<p>(Here by <span class="math-container">$\mathsf{AC}^1$</span> I mean  the class of decision problems solvable by a <em>uniform</em> family of Boolean circuits, with polynomial size, logarithmic depth , and unbounded fan-in.)</p>

CC BY-SA 4.0
2023-01-21T19:35:34.637Z
LOGCFL-complete problems such as [here](https://en.wikipedia.org/wiki/LOGCFL).
Emil Jeřábek
CC BY-SA 4.0
2023-01-21T19:43:18.457Z
I'd think that $O(\log n)$-width mazes should be $\mathsf{AC}^1$-complete (see here https://link.springer.com/chapter/10.1007/BFb0028550 for the problem definition and proof that they are complete for levels of the $\mathsf{AC}^0$ hierarchy). Any such complete problem won't be known to be in $\mathsf{NL}$.
Joshua Grochow
<cc.complexity-theory><complexity-classes><logspace><circuit-depth>
$\mathsf{NL}$ vs. $\mathsf{AC}^1$
Alexey Milovanov
# $\mathsf{NL}$ vs. $\mathsf{AC}^1$

(Asked by: username_0 on 2023-01-21)

It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem **PATH** belongs to $\mathsf{AC}^1$).

Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\mathsf{NL}?$

(Here by $\mathsf{AC}^1$ I mean the class of decision problems solvable by a *uniform* family of Boolean circuits, with polynomial size, logarithmic depth , and unbounded fan-in.)

**Tags:** cc.complexity-theory, complexity-classes, logspace, circuit-depth
> **Comments:**
> **username_1**: LOGCFL-complete problems such as [here](https://en.wikipedia.org/wiki/LOGCFL).  
> **username_2**: I'd think that $O(\log n)$-width mazes should be $\mathsf{AC}^1$-complete (see here https://link.springer.com/chapter/10.1007/BFb0028550 for the problem definition and proof that they are complete for levels of the $\mathsf{AC}^0$ hierarchy). Any such complete problem won't be known to be in $\mathsf{NL}$.  

---

## 0 answers

