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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.