<p>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.</p>

CC BY-SA 3.0
2012-11-27T16:10:03.863Z
This argument is correct if we are in model 3 (see my update) but otherwise y1+..+ym<=n^a is not necessarily true.
domotorp
CC BY-SA 3.0
2012-11-27T19:59:13.337Z
Yes, I was indeed having your model 3 in mind. Sorry for being imprecise.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-11-27T09:59:04.593Z
2012-11-27T09:59:04.593Z
Kristoffer Arnsfelt Hansen
<p>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 : </p>

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

<p>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}}$,</p>

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

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

CC BY-SA 3.0
2012-11-27T15:55:36.697Z
Hi, thx for the answer, but in fact this is the same as the proof I knew for the inclusion.
domotorp
CC BY-SA 3.0
2012-11-27T14:07:22.680Z
2012-11-27T14:07:22.680Z
Sajin Koroth
<p>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?</p>

<p>Update: There are three possible ways to define oracle machines.</p>

<p>1, They have an oracle tape, which they can read (see <a href="http://en.wikipedia.org/wiki/Oracle_machine" rel="nofollow">wikipedia</a>).</p>

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

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

<p>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.</p>

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

CC BY-SA 3.0
2012-11-26T23:45:08.263Z
DTIME(.) is a set. What does it mean to raise one set to the power of another?
Tyson Williams
CC BY-SA 3.0
2012-11-27T02:33:30.110Z
i think this is oracle notation
Sasho Nikolov
CC BY-SA 3.0
2012-11-27T17:16:56.197Z
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.
Sajin Koroth
CC BY-SA 3.0
2012-11-27T17:35:51.680Z
@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$.
Marzio De Biasi
CC BY-SA 3.0
2012-11-27T17:47:52.850Z
Yes, the tape head must be moved to reach the lex(y) location to read off $y\in L$. I was wrong in mentioning about writing down $y$, but note maximum y, you can query is lexicographically $cn^a$th in $\{0,1\}^*$ as machine runs in time $cn^a$, the sum of length of such $y$'s need not be bounded by $cn^a$ as you could query all the $cn^a$ lex-first strings in $\{0,1\}^*$ by moving the oracle tape always to the right. Even in this case $\sum_i |y_i| <= \frac{1}{2}cn^a(cn^a+1)$, implying that the resulting simulation is possible in $O(n^{2ab})$.
Sajin Koroth
CC BY-SA 3.0
2012-11-27T21:05:58.450Z
@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).
domotorp
CC BY-SA 3.0
2013-01-07T03:41:38.037Z
IIRC, the number of tapes only maters when it's less than two and when time is subquadratic.
Kaveh
<cc.complexity-theory><complexity-classes><oracles>
What is $DTIME(n^a)^{DTIME(n^b)}$?
domotorp
# What is $DTIME(n^a)^{DTIME(n^b)}$?

(Asked by: username_0 on 2012-11-26)

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](http://en.wikipedia.org/wiki/Oracle_machine)).

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

**Tags:** cc.complexity-theory, complexity-classes, oracles

> **Comments:**
> **username_1**: DTIME(.) is a set. What does it mean to raise one set to the power of another?  
> **username_2**: i think this is oracle notation  
> **username_3**: 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.  
> **username_4**: @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$.  
> **username_3**: Yes, the tape head must be moved to reach the lex(y) location to read off $y\in L$. I was wrong in mentioning about writing down $y$, but note maximum y, you can query is lexicographically $cn^a$th in $\{0,1\}^*$ as machine runs in time $cn^a$, the sum of length of such $y$'s need not be bounded by $cn^a$ as you could query all the $cn^a$ lex-first strings in $\{0,1\}^*$ by moving the oracle tape always to the right. Even in this case $\sum_i |y_i| <= \frac{1}{2}cn^a(cn^a+1)$, implying that the resulting simulation is possible in $O(n^{2ab})$.  
> **username_0**: @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).  
> **username_5**: IIRC, the number of tapes only maters when it's less than two and when time is subquadratic.  

---

## 2 answers

### Answer by username_6 on 2012-11-27. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: This argument is correct if we are in model 3 (see my update) but otherwise y1+..+ym<=n^a is not necessarily true.  
> **username_6**: Yes, I was indeed having your model 3 in mind. Sorry for being imprecise.  

---

### Answer by username_3 on 2012-11-27. Score: 5

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.

> **Comments:**
> **username_0**: Hi, thx for the answer, but in fact this is the same as the proof I knew for the inclusion.  

---

