# Nondeterminstic Linear Time vs Other Complexity Classes

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

• – Clement C. Aug 15 at 17:46
• @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)$? – Alex Williams Aug 15 at 17:50
• 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. – Alex Williams Aug 15 at 21:21
• @AlexWilliams - One of the answers suggests that it is still open weather NTIME(n)=E, which may imply that your question is difficult... – Avi Tal Aug 16 at 9:39
• 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. :) – Michael Wehar Aug 21 at 4:57