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?
$\begingroup$
$\endgroup$
4
-
11$\begingroup$ NTIME(n)⊆P is equivalent to P=NP by padding argument. $\endgroup$– Tsuyoshi ItoFeb 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$– Jeff BurdgesFeb 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$– Tsuyoshi ItoFeb 6, 2013 at 17:56
-
5$\begingroup$ @Tsuyoshi, could you post your comments as an answer so the question becomes answered? $\endgroup$– KavehFeb 6, 2013 at 19:45
Add a comment
|