<p>Arora and Barak's <a href="http://theory.cs.princeton.edu/complexity/book.pdf" rel="nofollow noreferrer">online book</a> claims in exercise 6.11 that $NC^1=L$. While the $NC^1\subset L$ direction is relatively straightforward and explained in many other texts, I couldn't prove or find the $L\subset NC^1$ direction anywhere. Since their book is just a draft, I was wondering if their claim was even true?</p>

<p>P.S. I apologize if this is not research-level. Just inform me in the comments and I will take it down if that is the case.</p>

CC BY-SA 3.0
2018-03-17T12:55:19.663Z
This is most certainly a typo for $\mathrm{NC^1\subseteq L}$. Anyway, $\mathrm{NC^1=L}$ is not known, and likely false.
Emil Jeřábek
CC BY-SA 3.0
2018-03-17T12:57:56.390Z
It's corrected in the published book (where it is 6.14).
Emil Jeřábek
<circuit-complexity><time-complexity>
Is $L\subset NC^1$
exfret
# Is $L\subset NC^1$

(Asked by: username_0 on 2018-03-17)

Arora and Barak's [online book](http://theory.cs.princeton.edu/complexity/book.pdf) claims in exercise 6.11 that $NC^1=L$. While the $NC^1\subset L$ direction is relatively straightforward and explained in many other texts, I couldn't prove or find the $L\subset NC^1$ direction anywhere. Since their book is just a draft, I was wondering if their claim was even true?

P.S. I apologize if this is not research-level. Just inform me in the comments and I will take it down if that is the case.

**Tags:** circuit-complexity, time-complexity
> **Comments:**
> **username_1**: This is most certainly a typo for $\mathrm{NC^1\subseteq L}$. Anyway, $\mathrm{NC^1=L}$ is not known, and likely false.  
> **username_1**: It's corrected in the published book (where it is 6.14).  

---

## 0 answers

