patternModerate
Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)
Viewed 0 times
dtimerosenbergunliketrueresults
Problem
I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says:
For all ε > 0, DTIME(O(n)) = DTIME( (1+ε) n).
Now I'm confused with this corollary and Rosenberg's result (p87 in the same book):
DTIME(n) ≠ DTIME(2n).
Why can we not use the corollary to show that DTIME(n) = DTIME(2n)?
For all ε > 0, DTIME(O(n)) = DTIME( (1+ε) n).
Now I'm confused with this corollary and Rosenberg's result (p87 in the same book):
DTIME(n) ≠ DTIME(2n).
Why can we not use the corollary to show that DTIME(n) = DTIME(2n)?
Solution
$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for some constant implicit in $O$, in other words, it is the union of the $\mathrm{DTIME}(cn)$ for all $c>0$. That this union is, in fact, equal to $\mathrm{DTIME}(cn)$ for any given $c>1$ (i.e., $1+\varepsilon$) means that all the $\mathrm{DTIME}(cn)$ for $c>1$ are equal, it does not say anything about $\mathrm{DTIME}(n)$, so there is no contradiction with the fact that $\mathrm{DTIME}(n)\neq \mathrm{DTIME}(2n)$ (although the results could have been stated in a clearer way).
Context
StackExchange Computer Science Q#57889, answer score: 10
Revisions (0)
No revisions yet.