Problem Detail: 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)?
Asked By : math
Answered By : Gro-Tsen
$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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/57889
