# Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

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?

• 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? Aug 4, 2015 at 15:51
• @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...!
– vzn
Aug 4, 2015 at 18:24

## 1 Answer

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)$.

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