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

Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theallaxiomatichierarchyworldstruetimethattheoremrelativized

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#34098, answer score: 7

Revisions (0)

No revisions yet.