Cheap and Secure Web Hosting Provider : See Now

[Solved]: Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

, , No Comments
Problem Detail: 

I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world. However, is it possible to prove that no oracles exist in which the Time Hierarchy Theorem fails? Or is it just that we have not been able to discover any, that we assume that the Time Hierarchy Theorem never fails. Thanks.

Asked By : Ari

Answered By : Yuval Filmus

The proof of the time hierarchy theorem relativizes. This means that all the steps remain true if all Turing machines are given access to the same oracle $O$ (for arbitrary $O$). This implies that the theorem itself remains true if all Turing machines are given access to the oracle $O$.

So yes, it is possible to prove that no oracles exist with respect to which the time hierarchy theorem fails.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/34098

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback