4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 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
    Aug 4, 2015 at 18:24

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 at 20:38

Your Answer

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

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