patternMinor
Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?
Viewed 0 times
whythentimehierarchytimecompletenondeterministicreductionsproblemsnot
Problem
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?
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?
Solution
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)$.
Context
StackExchange Computer Science Q#45007, answer score: 9
Revisions (0)
No revisions yet.