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$

closed as unclear what you're asking by David Richerby, Yuval Filmus, Evil, Discrete lizard, vonbrand Aug 1 '18 at 13:26

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.