Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
