This might be embarrassing, but it turned out I don't know what is $DTIME(n^a)^{DTIME(n^b)}$. It is between $DTIME(n^{ab})$ and $DTIME(n^{a(b+1)})$ but where?

Update: There are three possible ways to define oracle machines.

1, They have an oracle tape, which they can read (see wikipedia).

2, They have an oracle tape, from which they can pose questions (see Arora-Barak book).

3, Same as two, but after each question the tape is erased (I could swear I heard this too).

I had 2 in mind, as the most common (?) definition. In case of 3 it is easy to prove that the answer is $DTIME(n^{ab})$ (see Kristoffer's answer). In case of 1, I am not even sure that the bounds I claim hold, but maybe it is not hard to prove, I have no clue about this version.

Update: I have realized that the number of tapes changes the power, so it is best to forget this question...

  • 1
    $\begingroup$ DTIME(.) is a set. What does it mean to raise one set to the power of another? $\endgroup$ Commented Nov 26, 2012 at 23:45
  • 7
    $\begingroup$ i think this is oracle notation $\endgroup$ Commented Nov 27, 2012 at 2:33
  • $\begingroup$ Irrespective of how the oracle tape is defined @Kristoffer 's answer would hold, as the bound on number of queries do not change (the base machine is still $cn^a$ and hence can know the membership of at most $cn^a$ many inputs, and together their length cannot be more than $cn^a$ because the base machine can write only at most as many symbols as its running time). Hence the simulation described by Kristoffer would not be affected unless I am missing something. $\endgroup$ Commented Nov 27, 2012 at 17:16
  • $\begingroup$ @SajinKoroth: But it seems to me that in the (strange) model 1. every "call" to the oracle $A$ to check if $y \in A$ implies an exponential number of steps (of the oracle head that must be moved explicitly) to reach the position of the $y$-th element of the characteristic function of $A$. $\endgroup$ Commented Nov 27, 2012 at 17:35
  • 1
    $\begingroup$ @Sajin: The total length of the queries might be n^{2a} in model 2, as in the i'th step we can make a query of length i. This is why the best upper bound I know is a(b+1). $\endgroup$
    – domotorp
    Commented Nov 27, 2012 at 21:05

2 Answers 2


It seems your upper bound can be improved as follows: On input $x$ of length $n$, let $y_1,\dots,y_m$ be the oracle queries. Note that $|y_1|+\dots+|y_m| \leq c_1n^a$. The time to simulate the oracle machine to answer query $y_i$ is $c_2|y_i|^b$. Note now that $c_2(|y_1|^b+\dots+|y_m|^b) \leq c_2 (|y_1|+\dots+|y_m|)^b \leq c_2(c_1n^a)b = c_1c_2n^{ab}$. Thus the time to simulate the computation without the oracle is $c_1n^a + c_1c_2n^{ab} = O(n^{ab})$, which matches your lower bound.

  • $\begingroup$ This argument is correct if we are in model 3 (see my update) but otherwise y1+..+ym<=n^a is not necessarily true. $\endgroup$
    – domotorp
    Commented Nov 27, 2012 at 16:10
  • 1
    $\begingroup$ Yes, I was indeed having your model 3 in mind. Sorry for being imprecise. $\endgroup$ Commented Nov 27, 2012 at 19:59

You can also prove the other direction, i.e. $DTIME(n^{ab})\subseteq DTIME(n^a)^{DTIME(n^b)}$ using a padding argument, consider any $L\in DTIME(n^a)$ via some machine $M$ running in time $O(n^{ab})$. Let $L_{\text{pad}}=\left\{1^{n^a}\#x | x\in L \right\}$, $L_{\text{pad}}$ is in $DTIME(n^b)$ via the following algorithm :

  1. Remove $1^{n^a}\#$, and get $x$, if the input is not of this form reject.
  2. Run $M$ on $x$.

On input $y$ step 1 takes time linear in $|y|$, step 2 takes time $|x|^{ab}=\left(|x|^a\right)^b=|y|^b$. Hence $L{\text{pad}} \in DTIME(n^b)$. Given $x$, we can check whether $x\in L$ by the following oracle machine which has oracle access to $L_{\text{pad}}$,

  1. Write $1^{n^a}\#x$ on the oracle tape.
  2. Query $L_{\text{pad}}$ oracle, if it accepts accept $x$, otherwise reject $x$.

The base machine clearly runs in $DTIME(n^a)$ and, the oracle is in $DTIME(n^b)$ as proved earlier.

  • $\begingroup$ Hi, thx for the answer, but in fact this is the same as the proof I knew for the inclusion. $\endgroup$
    – domotorp
    Commented Nov 27, 2012 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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