Arora and Barak's online book 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.

  • 6
    $\begingroup$ This is most certainly a typo for $\mathrm{NC^1\subseteq L}$. Anyway, $\mathrm{NC^1=L}$ is not known, and likely false. $\endgroup$ – Emil Jeřábek Mar 17 '18 at 12:55
  • 6
    $\begingroup$ It's corrected in the published book (where it is 6.14). $\endgroup$ – Emil Jeřábek Mar 17 '18 at 12:57

Your Answer

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

Browse other questions tagged or ask your own question.