Problem Detail: 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.
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.
Asked By : Ari
Answered By : A.Schulz
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33989 Ask a Question Download Related Notes/Documents
