4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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
    Commented Mar 17, 2018 at 12:55
  • 6
    $\begingroup$ It's corrected in the published book (where it is 6.14). $\endgroup$
    – Emil Jeřábek
    Commented Mar 17, 2018 at 12:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.