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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
The problem with your reasoning is the precise definition of $RE$-completeness.
$RE$-complete is defined in terms of computable many-one reductions. This means that you may not be able to solve every question in $O(1)$ by applying the oracle, since you don't know how much time the reduction itself needs to take.
For completeness of the answer, on why we care about the type of reduction:
An oracle is defined to be a "black box" that can solve a single pre-defined language. For example, you can ask about an oracle to SAT, or Vertex-Cover. And you can ask about an oracle to the halting problem - but what you cannot do, is ask for an oracle of a family of languages. You might be confused since sometimes people say "oracle to NP" - what they really mean is an oracle to some NP-complete problem, say an oracle to SAT. Since NP-completeness is defined relative to polynomial reductions, this is not a problem to say you have an "oracle to NP".
-
$\begingroup$ But still this would imply that P = EXP relative to a halting oracle. Would it not? Unless it took greater then polynomial time to reduce an exp problem to the halting problem. Even if not you could get around this by replacing the halting oracle with a general RE oracle. $\endgroup$Colonizor48– Colonizor482021-12-17 23:55:27 +00:00Commented Dec 17, 2021 at 23:55
-
$\begingroup$ It can take more than poly time to reduce problems in EXP to the halting problem. And what do you mean by "general RE oracle"? An oracle is defined for a single language. $\endgroup$nir shahar– nir shahar2021-12-18 01:57:19 +00:00Commented Dec 18, 2021 at 1:57
-
$\begingroup$ @Colonizor48 It would not. There is no way to get around the relativized time hierarchy theorem: no matter what oracle $A$ you pick, there will be no efficient reduction of $\mathsf{EXP}^A$ to $\mathsf{P}^A$. (Note that "$\mathsf{P}^A\not=\mathsf{EXP}^A$" is different from "$A$ computes a polytime-reduction of $\mathsf{EXP}$ to $\mathsf{P}$.") $\endgroup$Noah Schweber– Noah Schweber2021-12-18 02:06:10 +00:00Commented Dec 18, 2021 at 2:06
-
$\begingroup$ @Noah Schweber What about an ALL oracle? $\endgroup$Colonizor48– Colonizor482021-12-18 02:10:19 +00:00Commented Dec 18, 2021 at 2:10
-
1$\begingroup$ @Colonizor48 An oracle is defined to be a "black box" that can solve a single pre-defined language. For example, you can ask about an oracle to SAT, or Vertex-Cover. And you can ask about an oracle to the halting problem - but what you cannot do, is ask for an oracle of a family of languages. You might be confused since sometimes people say "oracle to NP" - what they really mean is an oracle to some NP-complete problem, say an oracle to SAT. Since NP-completeness is defined relative to polynomial reductions, this is not a problem to say you have an "oracle to NP". $\endgroup$nir shahar– nir shahar2021-12-18 13:37:57 +00:00Commented Dec 18, 2021 at 13:37