<p>Check out this paper of 
<a href="http://www.iro.umontreal.ca/~mckenzie/mcrevi99.ps">McKenzie, Reinhardt, Vinay</a>. We use multiplex-select gates to characterize classes between $NC^1$ and $LOGCFL$, including $L$, $LOGDCFL$ etc. For example, $L = MWidth, Size(log,poly).$
</p>

<p>$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.</p>

CC BY-SA 2.5
2010-12-02T09:40:50.983Z
2010-12-02T09:40:50.983Z
V Vinay
<p>Well, $L = SC^1$, where $SC^1$ is the class of languages computed by polynomial size circuits of $O(\log n)$ width.</p>

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

CC BY-SA 3.0
2013-03-25T21:20:08.790Z
@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
CC BY-SA 3.0
2013-03-26T15:49:30.940Z
@Robin, I can't think of it, actually. Perhaps Vinay knows?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-03-26T17:49:26.047Z
Thanks. Maybe I'll just clarify the definition once again. I guess you mean polynomial size, log width circuits over unbounded fanin AND, OR, NOT gates, where the input of the circuit is $x$? And we enforce (say) log space uniformity, so that on input $1^n$ there is a log space TM that outputs the circuit $C_n$ which computes the function for all $n$-bit inputs $x$?
Robin Kothari
CC BY-SA 2.5
2010-12-02T09:11:19.857Z
We need the circuits to be uniform, right?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-02T09:14:35.217Z
Correct, they should be uniform.
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2010-12-02T13:27:59.633Z
[$SC^1$](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#sc) is defined using Turing Machines as $DTimeSpace(poly,log)$ so it is already uniform.
Kaveh
CC BY-SA 2.5
2010-12-02T08:50:24.903Z
2010-12-02T08:57:03.367Z
2010-12-02T08:57:03.367Z
Kristoffer Arnsfelt Hansen
<p>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.</p>

<blockquote>
  <p>So is there a circuit-based definition of L?</p>
</blockquote>

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

<p>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.</p>

CC BY-SA 2.5
2010-12-02T07:54:58.423Z
Do logarithmic sized circuits contain $L$?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-02T15:44:41.847Z
@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
<cc.complexity-theory><complexity-classes><circuit-complexity>
Does L have a definition in terms of circuits?
Robin Kothari
# Does L have a definition in terms of circuits?

(Asked by: username_0 on 2010-12-02)

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.

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity

> **Comments:**
> **username_1**: Do logarithmic sized circuits contain $L$?  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_3 on 2010-12-02. Score: 14 | Accepted answer

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

> **Comments:**
> **username_4**: We need the circuits to be uniform, right?  
> **username_3**: Correct, they should be uniform.  
> **username_5**: [$SC^1$](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#sc) is defined using Turing Machines as $DTimeSpace(poly,log)$ so it is already uniform.  
> **username_0**: @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?  
> **username_3**: @Robin, I can't think of it, actually. Perhaps Vinay knows?  
> **username_0**: Thanks. Maybe I'll just clarify the definition once again. I guess you mean polynomial size, log width circuits over unbounded fanin AND, OR, NOT gates, where the input of the circuit is $x$? And we enforce (say) log space uniformity, so that on input $1^n$ there is a log space TM that outputs the circuit $C_n$ which computes the function for all $n$-bit inputs $x$?  

---

### Answer by username_2 on 2010-12-02. Score: 13

Check out this paper of
[McKenzie, Reinhardt, Vinay](http://www.iro.umontreal.ca/~mckenzie/mcrevi99.ps). 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.


---

