5
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ $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. $\endgroup$
    – Turbo
    Commented Feb 8, 2023 at 18:41
  • $\begingroup$ $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...). $\endgroup$ Commented Feb 8, 2023 at 19:03
  • $\begingroup$ @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? $\endgroup$ Commented Feb 8, 2023 at 19:35
  • $\begingroup$ @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 $\endgroup$ Commented Feb 8, 2023 at 19:42
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Feb 9, 2023 at 7:28

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.