Problem Detail: 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?
Asked By : Sonu
Answered By : David Richerby
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 $Lin mathrm{NTIME}(n)$. You can only conclude that $Linmathrm{NTIME}(n^k)$ for some $k$ which, of course, you already knew from the assumption that $Linmathrm{NTIME}(n^3)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45007
