3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I believe you learned wrongly from that post, even though its answer is correct. $\;\;\;$ $\: \operatorname{DTIME}^{\operatorname{EXP}}(n^k) = \operatorname{EXP} \:$ and for each language $A$ in $\operatorname{EXP}$, $\:\: \operatorname{DTIME}^A(n^k) \neq \operatorname{EXP} \;\;$. $\;\;\;\;\;\;\;\;\;$ $\endgroup$ – user12859 Dec 10 '14 at 9:37
  • $\begingroup$ @Ricky But I thought that ${\sf DTIME}^{\text{EXP}}(n^k)$ is defined by ${{\sf DTIME}^A}(n^k)$ for any EXPTIME-complete language in $A \in \text{EXP}$ just like ${\text{NP}}^{\text{NP}}$ means ${\text{NP}}^{\text{SAT}}$. If not how is it defined? $\endgroup$ – Ari Dec 10 '14 at 13:40
  • $\begingroup$ It's defined like I said in this answer. $\;$ $\endgroup$ – user12859 Dec 10 '14 at 13:52
  • $\begingroup$ @Ricky I apologize but I am still missing the point: There you equated $P^B$ with $P^K$ for a language $K$ which is complete in a complexity class $B$ whereas in your comment above you seem to be drawing a distinction between ${\sf DTIME}^{\text{EXP}}(n^k)$ and ${\sf DTIME}^A(n^k)$ for any $A \in \text{EXP}$ and this would include EXPTIME-complete languages. Is it just that ${\sf DTIME}(n^k) \neq P$ for any fixed $k$ or am I missing out on another point? $\endgroup$ – Ari Dec 11 '14 at 2:06
  • $\begingroup$ I "equated $P^B$ with $P^K$ for a language $K$ which is complete in a complexity class $B$" under polynomial-time Turing reductions. $\:$ In my "comment above" I was "drawing a distinction between $\operatorname{DTIME}^{\operatorname{EXP}}(n^k)$ and $\operatorname{DTIME}^A(n^k)$ for any $A\in \operatorname{EXP}$" because languages are not complete for EXPTIME under $n^k$-time Turing reductions. $\;\;\;\;$ $\endgroup$ – user12859 Dec 11 '14 at 3:41
7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ And, to answer the question in the title, no, it is not axiomatic: it's a theorem. $\endgroup$ – David Richerby Dec 10 '14 at 9:39

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.