1
$\begingroup$

How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$?

(sorry about how it is written. I mean the set of languages decided by a deterministic TM with an oracle to $\mathrm{Htm}$ in $n^2$ time and $n^3$ time).

If someone can please write the proof, it will be great.

$\endgroup$
  • 2
    $\begingroup$ What do you mean by Htm? $\endgroup$ – xskxzr Jul 22 '18 at 5:14
  • $\begingroup$ I'm voting to close as unclear: Htm still hasn't been defined and the asker has been absent from the site for nearly a month. $\endgroup$ – David Richerby Jul 22 '18 at 11:45
1
$\begingroup$

A language is in $\mathsf{DTIME}(f(n))$ if there is a Turing machine accepting the language and running in time at most $f(n)$ (or, in some definitions, $O(f(n))$). Therefore $f(n) \leq g(n)$ implies that $\mathsf{DTIME}(f(n)) \subseteq \mathsf{DTIME}(g(n))$. The same holds for relativized classes.

$\endgroup$
  • $\begingroup$ Thanks! I missed a small detail in the question which makes it different... I meant contained but not equal :) $\endgroup$ – koral Jun 21 '18 at 18:52
  • $\begingroup$ This is the well-known time hierarchy theorem. Wikipedia contains a proof. $\endgroup$ – Yuval Filmus Jun 21 '18 at 18:54
  • $\begingroup$ @koral Please edit your question to include that crucial information, as well as the definition of "Htm". $\endgroup$ – David Richerby Jul 22 '18 at 11:45

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