Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, $\mathrm{L} \in \mathrm{NTIME}(n)$. Thus, $\mathrm{NTIME}(n^3)\subseteq \mathrm{NTIME}(n)$ which implies the non-deterministic time-hierarchy is false.

But we all know that time hierarchy is true. Where am I going wrong? The statement seems to be correct but I know it's wrong. How?

  • 3
    $\begingroup$ Is SAT actually in NTIME(n)? I've never heard that before and suspect that due to encoding issues it would be very difficult to design a linear-time NTM for it. Do you have a source for that? $\endgroup$ – templatetypedef Aug 4 '15 at 15:51
  • $\begingroup$ @template iirc/ afaik cook's proof is not nondeterministic linear time (NTIME(n)) and the polynomial power is actually calculated somewhere, possibly even in the original paper...! $\endgroup$ – vzn Aug 4 '15 at 18:24

The reduction takes time to perform. You know that time is polynomial but you don't know it's linear so you can't conclude that $L\in \mathrm{NTIME}(n)$. You can only conclude that $L\in\mathrm{NTIME}(n^k)$ for some $k$ which, of course, you already knew from the assumption that $L\in\mathrm{NTIME}(n^3)$.

  • $\begingroup$ For $L$ we have assumed that $L \in NTIME(n^k)$ but I want to know the false relation in the above specified relations. $\endgroup$ – Pragya Aug 4 '15 at 20:36
  • 2
    $\begingroup$ @user35651 My answer already says that: the false claim is "Hence, $L\in\mathrm{NTIME}(n)$." $\endgroup$ – David Richerby Aug 4 '15 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.