3
$\begingroup$

I knew that $P \neq EXP$ by Time Hierarchy Theorem. But, I'd like to show that $P^A \neq EXP^A$ for all oracles A. How can I do it?

I knew that If I make A=EXP, PSPACE, NP, and many others, then this would show that the inequality holds. But, how can I prove it for all oracles? Can you give me hints?

Notes: I don't think that there exists some oracle that $P^B = EXP^B$ for some oracles B since it seems to me that $P \neq EXP$ using THT relativizes. But I don't know why it relativizes? Consider this as a minor question of the above question.

$\endgroup$
0
3
$\begingroup$

Why does the proof of the time hierarchy theorem relativize? The time hierarchy theorem is proved by diagonalization. Such proofs tend to relativize. In order to know for sure, all you have to do is to repeat the proof of the time hierarchy theorem, when all concerned Turing machines are oracle Turing machines having access to the same oracle. If the proof still goes through, then it relativizes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.