<p>Is it known whether or not nondeterministic linear time contains <span class="math-container">$P$</span> and/or smaller classes such as Uniform-<span class="math-container">$NC^1$</span>?</p>

CC BY-SA 4.0
2019-08-15T17:46:48.453Z
Relevant: https://cstheory.stackexchange.com/questions/16385/nondeterministic-linear-time-vs-the-deterministic-time-hierarchy
Clement C.
CC BY-SA 4.0
2019-08-15T17:50:23.923Z
@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
CC BY-SA 4.0
2019-08-15T21:21:44.427Z
Considering that [Cook](https://core.ac.uk/download/pdf/82028132.pdf) 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](https://link.springer.com/article/10.1007/BF01705890) implies $NC^1\subset NTIME(n)$.  However, I'm not sure how the reduction argument would go.
Alex Williams
CC BY-SA 4.0
2019-08-16T01:44:46.660Z
You may find this helpful: https://cstheory.stackexchange.com/questions/40801/are-there-languages-in-dtime2tn-that-are-not-in-ntimetn
Avi Tal
CC BY-SA 4.0
2019-08-16T04:47:04.107Z
@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
CC BY-SA 4.0
2019-08-16T09:39:27.140Z
@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
CC BY-SA 4.0
2019-08-21T04:57:04.147Z
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
<cc.complexity-theory><time-complexity>
Nondeterminstic Linear Time vs Other Complexity Classes
Alex Williams
# Nondeterminstic Linear Time vs Other Complexity Classes

(Asked by: username_0 on 2019-08-15)

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

**Tags:** cc.complexity-theory, time-complexity

> **Comments:**
> **username_1**: Relevant: https://cstheory.stackexchange.com/questions/16385/nondeterministic-linear-time-vs-the-deterministic-time-hierarchy  
> **username_0**: @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)$?  
> **username_0**: Considering that [Cook](https://core.ac.uk/download/pdf/82028132.pdf) 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](https://link.springer.com/article/10.1007/BF01705890) implies $NC^1\subset NTIME(n)$.  However, I'm not sure how the reduction argument would go.  
> **username_2**: You may find this helpful: https://cstheory.stackexchange.com/questions/40801/are-there-languages-in-dtime2tn-that-are-not-in-ntimetn  
> **username_0**: @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.  
> **username_2**: @AlexWilliams - One of the answers suggests that it is still open weather NTIME(n)=E, which may imply that your question is difficult...  
> **username_3**: 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.  :)  

---

## 0 answers

