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

Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

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

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.