Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
7
-
$\begingroup$ Relevant: cstheory.stackexchange.com/questions/16385/… $\endgroup$– Clement C.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$– Alex WilliamsAug 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$– Alex WilliamsAug 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 TalAug 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$– Michael WeharAug 21, 2019 at 4:57
|
Show 2 more comments