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$ Commented Aug 4, 2015 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
    Commented Aug 4, 2015 at 18:24

1 Answer 1


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
    Commented Aug 4, 2015 at 20:36
  • 2
    $\begingroup$ @user35651 My answer already says that: the false claim is "Hence, $L\in\mathrm{NTIME}(n)$." $\endgroup$ Commented Aug 4, 2015 at 20:38

Your Answer

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

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