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?

  • 11
    $\begingroup$ NTIME(n)⊆P is equivalent to P=NP by padding argument. $\endgroup$ Feb 6, 2013 at 12:23
  • $\begingroup$ Ahh wonderful, that answers my question very quickly! I shouldn't really need the other part of the question at this point. Thank you! $\endgroup$ Feb 6, 2013 at 13:32
  • 4
    $\begingroup$ 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.) $\endgroup$ Feb 6, 2013 at 17:56
  • 5
    $\begingroup$ @Tsuyoshi, could you post your comments as an answer so the question becomes answered? $\endgroup$
    – Kaveh
    Feb 6, 2013 at 19:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.