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?

Improve this question
$\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
    Feb 8 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$
    – Joshua Grochow
    Feb 8 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$
    – Alexey Milovanov
    Feb 8 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$
    – Joshua Grochow
    Feb 8 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$
    – Emil Jeřábek
    Feb 9 at 7:28

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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