<p>How much is known about nondeterministic linear time?  I'm <a href="https://ieeexplore.ieee.org/abstract/document/4568107" rel="nofollow noreferrer">aware</a> that <span class="math-container">$$ \mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$</span>
Is there an <span class="math-container">$m &gt; 1$</span> so that <span class="math-container">$\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$</span>?  Are there any arguments that <span class="math-container">$\mathrm{NTIME}(n) \subset \mathrm{P}$</span> should be unlikely?</p>

CC BY-SA 3.0
2013-02-06T12:23:19.753Z
NTIME(n)⊆P is equivalent to P=NP by padding argument.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-06T13:32:21.287Z
Ahh wonderful, that answers my question very quickly!  I shouldn't really need the other part of the question at this point.  Thank you!
Jeff Burdges
CC BY-SA 3.0
2013-02-06T17:56:16.313Z
And no value k>1 is known such that NTIME(n)⊈DTIME(n^k), because even a value k>1 with a weaker condition NTIME(n^k)⊈DTIME(n^k) is not known.  See [this question](http://cstheory.stackexchange.com/q/1079) by Bruno and the answer by Ryan Williams.  (The linked question only talks about k≥2, but if we knew that NTIME(n^k)⊈DTIME(n^k) for some noninteger k between 1 and 2, then we would also know NTIME(n^2)⊈DTIME(n^2) again by padding argument.)
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-06T19:45:53.900Z
@Tsuyoshi, could you post your comments as an answer so the question becomes answered?
Kaveh
CC BY-SA 4.0
2024-10-06T14:45:49.630Z
NTIME(n) and P (or NP) are incomparable because NTIME(n) is not closed under reductions
PsySp
<cc.complexity-theory><time-complexity><nondeterminism>
Nondeterministic linear time vs. the deterministic time hierarchy
Jeff Burdges
# Nondeterministic linear time vs. the deterministic time hierarchy

(Asked by: username_0 on 2013-02-06)

How much is known about nondeterministic linear time? I'm [aware](https://ieeexplore.ieee.org/abstract/document/4568107) that $$ \mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$
Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$? Are there any arguments that $\mathrm{NTIME}(n) \subset \mathrm{P}$ should be unlikely?

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

> **Comments:**
> **username_1**: NTIME(n)⊆P is equivalent to P=NP by padding argument.  
> **username_0**: Ahh wonderful, that answers my question very quickly!  I shouldn't really need the other part of the question at this point.  Thank you!  
> **username_1**: And no value k>1 is known such that NTIME(n)⊈DTIME(n^k), because even a value k>1 with a weaker condition NTIME(n^k)⊈DTIME(n^k) is not known.  See [this question](http://cstheory.stackexchange.com/q/1079) by Bruno and the answer by Ryan Williams.  (The linked question only talks about k≥2, but if we knew that NTIME(n^k)⊈DTIME(n^k) for some noninteger k between 1 and 2, then we would also know NTIME(n^2)⊈DTIME(n^2) again by padding argument.)  
> **username_2**: @Tsuyoshi, could you post your comments as an answer so the question becomes answered?  
> **username_3**: NTIME(n) and P (or NP) are incomparable because NTIME(n) is not closed under reductions  

---

## 0 answers

