# Does L have a definition in terms of circuits?

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.

• Do logarithmic sized circuits contain $L$? – Mohammad Al-Turkistany Dec 2 '10 at 7:54
• @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. – Robin Kothari Dec 2 '10 at 15:44

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

• We need the circuits to be uniform, right? – Hsien-Chih Chang 張顯之 Dec 2 '10 at 9:11
• Correct, they should be uniform. – Kristoffer Arnsfelt Hansen Dec 2 '10 at 9:14
• $SC^1$ is defined using Turing Machines as $DTimeSpace(poly,log)$ so it is already uniform. – Kaveh Dec 2 '10 at 13:27
• @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? – Robin Kothari Mar 25 '13 at 21:20
• @Robin, I can't think of it, actually. Perhaps Vinay knows? – Kristoffer Arnsfelt Hansen Mar 26 '13 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.