Are any two complexity classes equipped with an oracle to solve the halting problem equivalent?

Question

Equip any complexity classes $C$ and $B$ (to be more specific: any complexity classes that contain only decidable problems) with the same oracle $O$ that solves the halting problem for a Turing Machine. Is $C^O = B^O$ for any $B$ and $C$ that, again, only contain problems decidable by a TM with no access to an oracle (only the empty oracle)?

Answer 1

No, they are not in general - and focusing on the halting problem specifically makes the situation look more complicated than it actually is. The real point is the following:

There are lots of separation results which relativize to all oracles.

There's a slight technical issue here, actually: how exactly should we treat space-based complexity classes in the oracle context? See the bottom of page $5$ here. I'll only talk about time-based classes here to avoid having to think about this.

For example, the classical argument that $\mathsf{P}\subsetneq\mathsf{EXPTIME}$ in fact shows that $$\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$$ for every oracle $A$. In particular, we can take $A$ to be the Halting Problem. Another example of a separation which relativizes to all oracles - including the halting problem - is the time hierarchy theorem.

This topic is treated in chapter $3$ of Arora/Barak:

"Any result about TMs or complexity classes that uses only Properties I and II above also holds for the set of all TMs with oracle $A$. Such results are called relativizing results. All of the results on universal Turing machines and the diagonalizations results in this chapter are of this type."

(pg. 72; I've replaced their "$O$" with an "$A$" to avoid conflict with your use of "$O$" for the halting problem specifically.)

Of course not everything relativizes - and see in particular Baker-Gill-Solovay - but some things do relativize, and all relativizing separation results yield negative answers to the OP as special cases.

---

Just for completeness, here's one proof that $\mathsf{P}^A\not=\mathsf{EXPTIME}^A$ for any oracle $A$ goes; unsurprisingly, it's a direct diagonalization. Fix an oracle $A$; we want to show $\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$. We'll use an exponential-time machine with oracle $A$ to diagonalize against polytime machines with oracle $A$. Fix appropriate enumerations $(\Phi_i)_{j\in\mathbb{N}}$ and $(p_j)_{j\in\mathbb{N}}$ of oracle machines and polynomials respectively and an appropriate pairing function $\langle\cdot,\cdot\rangle$, and let $$X=\{\langle a,b\rangle: \neg\Phi_a^A(\langle a,b\rangle)[p_b(\lfloor\log (\langle a,b\rangle)\rfloor)]\downarrow=1\}$$ (here "$[s]\downarrow=$" means "halts in $s$ steps and equals"). By construction we have that $X\not\in \mathsf{P}^A$ (suppose $\Phi_a^A$ decided it in time $p_b$ ...); however, the "brute force" calculation of $X$ from $A$ only takes exponential time, so $X\in \mathsf{EXPTIME}^A$.

Note that this is just the usual proof, with an "$A$" superscript added everywhere. The point is that diagonalization is such a "coarse" technique that - when it works at all - it tends to work for all objects like Turing machines. And this includes Turing machines relative to a fixed oracle.

Answer 2

No. Consider $RE^O = \Sigma^2_0 \neq \Pi^2_0 = (coRE)^O $.

Thanks @Noah Schweber for pointing out a big mistake in my original answer. See his answer for a much more general treatment of the question.

Answer 3

If I have understood your question correctly, the answer would be no.

Here is a counterexample: Let C be the complexity class of finite state automata. The halting problem for C is thus computable by a turing machine, hence the problems that C^O can solve is a subset of the problems that a turing machine can solve. Let B be the complexity class of turing machines. The halting problem for B is not computable by a turing machine, hence B^O contains problems that C^O does not, and hence B^O and C^O are not equivalent.

As it turns out I have misunderstood your question.

If you meant for both oracles to be able to solve the halting problem for any turing machine, the answer is that they are equal. This is because an oracle for the turing machine can solve any problem a turing machine can solve, as it the oracle can just compute whether a turing machine would return a certain result for a certain input.