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)?


3 Answers 3


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.

  • $\begingroup$ The way you separate P from EXPTIME happens to coincide with the proof of the time hierarchy theorem. $\endgroup$ Commented May 23, 2020 at 7:53

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.

  • $\begingroup$ Nice, but $RE$ is not decidable--it is semi-decidable. Do you have a counter-example for any choice of complexity classes that contain only decidable problems? ex: $BQP^O \neq NP^O$. $\endgroup$
    – DeeDee
    Commented May 23, 2020 at 0:01
  • $\begingroup$ Then it depends on how do you define access to the Oracle. If it is through a second tape, where whenever you have a codification of machine and string written, you call the oracle and get an answer (by having states that represents these things), then I bet DSPACE(O(1))^O != PSPACE^O, because you could at most ask the oracle on constant size machines on DSPACE(O(1)), but for them in order to be useful on PSPACE problems you would need to design a machine based on the input and then ask the oracle whether it halts or not. $\endgroup$ Commented May 23, 2020 at 0:44
  • $\begingroup$ Note that two classes below RE, but big enough to actually write a TM based on the input and access the oracle on it, will immediately gain the power of RE when equipped with the oracle, and thus will become equal. $\endgroup$ Commented May 23, 2020 at 2:15
  • $\begingroup$ Thanks @Noah, my mistake was precisely what you asked me to remember; I was thinking on just being able to get positive answers from the oracle. Will fix the answer. $\endgroup$ Commented May 23, 2020 at 5:35
  • $\begingroup$ I've deleted my comment. (Note that since the OP asked for relativizations of subclasses of $REC$, this still isn't fully an answer, but it is a very important point on its own and absolutely worth mentioning in this context.) $\endgroup$ Commented May 23, 2020 at 5:46

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.

  • 1
    $\begingroup$ Your Os are not the same O. I meant to have both complexity classes equipped with the same oracle--an oracle powerful enough to solve the halting problem for a Turing Machine. I did not mean equip one with O to solve halting problem for one type of machine and equip the other with O to solve halting problem for another type of machine. Do you know the answer for when O = O, when they are both the same type of oracle (the type that solves halting problem for Turing Machine) Thanks! $\endgroup$
    – DeeDee
    Commented May 22, 2020 at 13:10
  • $\begingroup$ I edited question to make this clear. $\endgroup$
    – DeeDee
    Commented May 22, 2020 at 13:20
  • $\begingroup$ @RingRing I have edited my example. $\endgroup$ Commented May 22, 2020 at 21:50
  • 1
    $\begingroup$ I don't think this answer is correct, check mine. $\endgroup$ Commented May 22, 2020 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.