HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Confusion about the Time Hierarchy Theorem and relativization

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#33989, answer score: 8

Revisions (0)

No revisions yet.