Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
Asked
Active
Viewed 241 times
6
-
Relevant: https://cstheory.stackexchange.com/questions/16385/nondeterministic-linear-time-vs-the-deterministic-time-hierarchy – Clement C. Aug 15 '19 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 '19 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 '19 at 21:21
-
You may find this helpful: https://cstheory.stackexchange.com/questions/40801/are-there-languages-in-dtime2tn-that-are-not-in-ntimetn – Avi Tal Aug 16 '19 at 01:44
-
@AviTal. Thank you for the link. Unfortunately, it doesn't quite address my question since I'm interested in polynomial time (or classes in $P$) rather than exponential time. – Alex Williams Aug 16 '19 at 04:47
-
2@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 '19 at 09:39
-
1Hi @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 '19 at 04:57