[Solved]: Confusion about the Time Hierarchy Theorem and relativization

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.

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