Skip to main content
Computer Science

Return to Question

deleted 4 characters in body
Source Link
Colonizor48
Colonizor48
  • 239
  • 1
  • 6

I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) Hopefully you get the idea.. Isn't the time hierarchy theorem supposed to hold relative to every oracle, but here it seems as if every single complexity class collapses into whatever class O(1) is. I'm probably wrong here in some context. I'm very new to this so if you down-vote please explain why. Thanks.

I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) Hopefully you get the idea.. Isn't the time hierarchy theorem supposed to hold relative to every oracle, but here it seems as if every single complexity class collapses into whatever class O(1) is. I'm probably wrong here in some context. I'm very new to this so if you down-vote please explain why. Thanks.

I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) Hopefully you get the idea.. Isn't the time hierarchy theorem supposed to hold relative to every oracle, but here it seems as if every single complexity class collapses into whatever class O(1) is. I'm probably wrong here in some context. I'm very new to this so if you down-vote please explain why.

Source Link
Colonizor48
Colonizor48
  • 239
  • 1
  • 6

If the time hierarchy theorem holds relative to every oracle, what about a halting(RE) oracle?

I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) Hopefully you get the idea.. Isn't the time hierarchy theorem supposed to hold relative to every oracle, but here it seems as if every single complexity class collapses into whatever class O(1) is. I'm probably wrong here in some context. I'm very new to this so if you down-vote please explain why. Thanks.