5
$\begingroup$

I know that $\mathsf{P}^A = \mathsf{EXP}$ for any $\mathsf{EXPTIME}$-complete language $A$.

Is it true that $\mathsf{DTIME}^A(n^k) = \mathsf{EXP}$ for any fixed $k$ and any $\mathsf{EXPTIME}$-complete oracle $A$?
If not, what do these complexity classes equal and why?

I am just confused because then it seems to me that we would then have $\mathsf{DTIME}^A(n^k) = \mathsf{DTIME}^A(n^j)$ for $k < j$ and this would contradict the fact that the Time Hierarchy Theorem holds under any oracle.

$\endgroup$
7
$\begingroup$

It is not true that for $A$ being $\sf EXP$-complete ${\sf DTIME}^A(n^k) = {\sf EXP}$, but you are right with ${\sf P}^A={\sf EXP}$.

Here is the reason for this. In order to make use of the oracle you have to transform your problem via a reduction. This reduction is a polynomial reduction. The running time of this particular reduction might need $\omega(n^k)$ steps. In this case you cannot use the oracle in the desired way.

As you already observed ${\sf DTIME}^A(n^k) \neq {\sf EXP}$ because this would imply for all $k,j$ that ${\sf DTIME}^A(n^k)={\sf DTIME}^A(n^j)$, which cannot be true since the time hierarchy theorem relativizes.

$\endgroup$
  • 1
    $\begingroup$ Thanks. I just wish that textbook writers were more explicit on how oracle Turing Machines work (or don't work) so I could have avoided this confusion in the first place. $\endgroup$ – Ari Dec 7 '14 at 19:44

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.