13
$\begingroup$

Many complexity classes defined with Turing machines have definitions in terms of uniform circuits. For example, P can also be defined using uniform polynomial size circuits, and similarly BPP, NP, BQP, etc. can be defined with uniform circuits.

So is there a circuit-based definition of L?

An obvious idea would be to allow polynomial size circuits with some depth limitation, but this turn out to define the NC hierarchy.

I was thinking about this question a long time ago, but didn't find an answer. If I remember correctly, my motivation was to understand what the quantum analog of L would look like.

Improve this question
$\endgroup$
2
  • $\begingroup$ Do logarithmic sized circuits contain $L$? $\endgroup$
    – Mohammad Al-Turkistany
    Dec 2 '10 at 7:54
  • $\begingroup$ @Turkistany: No, I don't think so, since a log size circuit can at most have log depth, and thus is contained in NC_1, which is defined as log depth, poly size circuits. NC_1 is contained in L, and not known to be equal to L. $\endgroup$
    – Robin Kothari
    Dec 2 '10 at 15:44
13
$\begingroup$

Well, $L = SC^1$, where $SC^1$ is the class of languages computed by polynomial size circuits of $O(\log n)$ width.

As for $NL$, it could be characterized as the class languages computed by polynomial size skew circuits (which in some sense is just another way of saying nondeterministic branching programs).

Improve this answer
$\endgroup$
6
  • $\begingroup$ We need the circuits to be uniform, right? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 2 '10 at 9:11
  • $\begingroup$ Correct, they should be uniform. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Dec 2 '10 at 9:14
  • $\begingroup$ $SC^1$ is defined using Turing Machines as $DTimeSpace(poly,log)$ so it is already uniform. $\endgroup$
    – Kaveh
    Dec 2 '10 at 13:27
  • $\begingroup$ @KristofferArnsfeltHansen: It's been a while since you've answered this, but do you have a reference where the equivalence between the circuit and TM definitions of L is proved? $\endgroup$
    – Robin Kothari
    Mar 25 '13 at 21:20
  • $\begingroup$ @Robin, I can't think of it, actually. Perhaps Vinay knows? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Mar 26 '13 at 15:49
12
$\begingroup$

Check out this paper of McKenzie, Reinhardt, Vinay. We use multiplex-select gates to characterize classes between $NC^1$ and $LOGCFL$, including $L$, $LOGDCFL$ etc. For example, $L = MWidth, Size(log,poly).$

$NL$ has a natural circuit based characterization using Skew Circuits. This is just a circuit representation of the branching program that represents $NL$. Skew circuits are due to Venkateswaran.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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