Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?

  • $\begingroup$ Relevant: cstheory.stackexchange.com/questions/16385/… $\endgroup$
    – Clement C.
    Commented Aug 15, 2019 at 17:46
  • $\begingroup$ @ClementC. I agree that post is related. However, I'm interested in the opposite containment, i.e. is $P\subset NTIME(n)$ or $NC^1\subset NTIME(n)$? $\endgroup$ Commented Aug 15, 2019 at 17:50
  • $\begingroup$ Considering that Cook proved $NTIME(n^r)\subsetneq NTIME(n^s)$ for $1<=r < s$, I'm assuming the containment for $P$ is not known. However, the case $NC^1$ is rather interesting. I suspect Quasi-Realtime Languages implies $NC^1\subset NTIME(n)$. However, I'm not sure how the reduction argument would go. $\endgroup$ Commented Aug 15, 2019 at 21:21
  • 2
    $\begingroup$ @AlexWilliams - One of the answers suggests that it is still open weather NTIME(n)=E, which may imply that your question is difficult... $\endgroup$
    – Avi Tal
    Commented Aug 16, 2019 at 9:39
  • 1
    $\begingroup$ Hi @AlexWilliams Recently, I've been wondering if $P$ could be contained in non-deterministic linear time with bounded non-determinism. I have a few related results. I would be happy to discuss if you're interested. :) $\endgroup$ Commented Aug 21, 2019 at 4:57


Your Answer

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