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.
$\begingroup$
$\endgroup$
5
-
$\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$– user12859Commented Dec 10, 2014 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$– AriCommented Dec 10, 2014 at 13:40
-
$\begingroup$ It's defined like I said in this answer. $\;$ $\endgroup$– user12859Commented Dec 10, 2014 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$– AriCommented Dec 11, 2014 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$– user12859Commented Dec 11, 2014 at 3:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Dec 10, 2014 at 6:37
-
2$\begingroup$ And, to answer the question in the title, no, it is not axiomatic: it's a theorem. $\endgroup$ Commented Dec 10, 2014 at 9:39