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.
    Aug 15 '19 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$ Aug 15 '19 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$ Aug 15 '19 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
    Aug 16 '19 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$ Aug 21 '19 at 4: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.