6

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?

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

0 Answers0