patternMinor
Confusion about the Time Hierarchy Theorem and relativization
Viewed 0 times
therelativizationhierarchyandtimeabouttheoremconfusion
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#33989, answer score: 8
Revisions (0)
No revisions yet.