7
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ DTIME(.) is a set. What does it mean to raise one set to the power of another? $\endgroup$ – Tyson Williams Nov 26 '12 at 23:45
  • 7
    $\begingroup$ i think this is oracle notation $\endgroup$ – Sasho Nikolov Nov 27 '12 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$ – Sajin Koroth Nov 27 '12 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$ – Marzio De Biasi Nov 27 '12 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 Nov 27 '12 at 21:05
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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 Nov 27 '12 at 16:10
  • 1
    $\begingroup$ Yes, I was indeed having your model 3 in mind. Sorry for being imprecise. $\endgroup$ – Kristoffer Arnsfelt Hansen Nov 27 '12 at 19:59
5
$\begingroup$

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.

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

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.