5
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ How do they define $\sf DTIME$? $\endgroup$ – A.Schulz May 26 '16 at 11:33
  • $\begingroup$ We use on-line multitape turing machine whose input is written on one of the work tapes, DTIME(T(n)) is the set of all languages having time complexity T(n). if $L \in DTIME(T(n))$ and $L= L(M)$, that means M is determenistic turing machine and makes at most T(n) moves before halting. $\endgroup$ – Yuval May 26 '16 at 11:44
9
$\begingroup$

$\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).

$\endgroup$
  • 2
    $\begingroup$ So the first quote implies DTIME(n) ⊆ DTIME(2n) but not the reverse. (Aaand I make another notch in the "needless abuse of Landau notation leads to confusion" post.) $\endgroup$ – Raphael May 26 '16 at 13:40
  • 2
    $\begingroup$ In my algorithmica class we 'd have defined something like $DLINTIME = \bigcup_{c < 0}{DTIME(cn)}$ and then stated the corollary as $\forall \epsilon > 0 . DLINTIME = DTIME((1+\epsilon)n)$. $\endgroup$ – Bakuriu May 26 '16 at 14:03
  • $\begingroup$ @Bakuriu For $c<0$? ;) But yes, I agree that that is a nicer way of putting it. $\endgroup$ – Raphael May 26 '16 at 18:47
-2
$\begingroup$

In a purely mathematical sense, if n = 0, than DTIME(n) DOES = DTIME(2n), because 0 multiplied by any number = 0. So, if n = 0, DTIME(n) = DTIME(2n).

I dont know if this helps, but I hope it does.

$\endgroup$
  • 2
    $\begingroup$ "$n$" is a symbolic variable here, not something you get to insert numbers for. In particular, the whole concept of DTIME is only defined for $n \to \infty$. $\endgroup$ – Raphael May 26 '16 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.