# Nondeterministic linear time vs. the deterministic time hierarchy

How much is known about nondeterministic linear time? I'm aware 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?

• NTIME(n)⊆P is equivalent to P=NP by padding argument. – Tsuyoshi Ito Feb 6 '13 at 12:23
• 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 Feb 6 '13 at 13:32
• 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 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 Feb 6 '13 at 17:56
• @Tsuyoshi, could you post your comments as an answer so the question becomes answered? – Kaveh Feb 6 '13 at 19:45