HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?

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.