Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?
-
01-11-2019 - |
Pergunta
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.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange