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.

  • $\begingroup$ Do logarithmic sized circuits contain $L$? $\endgroup$ Commented Dec 2, 2010 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$ Commented Dec 2, 2010 at 15:44

2 Answers 2


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

  • $\begingroup$ We need the circuits to be uniform, right? $\endgroup$ Commented Dec 2, 2010 at 9:11
  • $\begingroup$ Correct, they should be uniform. $\endgroup$ Commented Dec 2, 2010 at 9:14
  • $\begingroup$ $SC^1$ is defined using Turing Machines as $DTimeSpace(poly,log)$ so it is already uniform. $\endgroup$
    – Kaveh
    Commented Dec 2, 2010 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$ Commented Mar 25, 2013 at 21:20
  • $\begingroup$ @Robin, I can't think of it, actually. Perhaps Vinay knows? $\endgroup$ Commented Mar 26, 2013 at 15:49

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.


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.