4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ LOGCFL-complete problems such as here. $\endgroup$
    – Emil Jeřábek
    Commented Jan 21, 2023 at 19:35
  • 4
    $\begingroup$ I'd think that $O(\log n)$-width mazes should be $\mathsf{AC}^1$-complete (see here 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}$. $\endgroup$
    – Joshua Grochow
    Commented Jan 21, 2023 at 19:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.