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$
5
-
12$\begingroup$ NTIME(n)⊆P is equivalent to P=NP by padding argument. $\endgroup$– Tsuyoshi ItoCommented 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$– Jeff BurdgesCommented 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$– Tsuyoshi ItoCommented Feb 6, 2013 at 17:56
-
5$\begingroup$ @Tsuyoshi, could you post your comments as an answer so the question becomes answered? $\endgroup$– KavehCommented Feb 6, 2013 at 19:45
-
$\begingroup$ NTIME(n) and P (or NP) are incomparable because NTIME(n) is not closed under reductions $\endgroup$– PsySpCommented Oct 6 at 14:45
Add a comment
|