# Can two different complexity classes be equal relative to an oracle? Example request

Is there a known example of two complexity classes, $A$ and $B$, such that:

1. $A \neq B$;

2. there is an oracle $O$ for which $A^O = B^O$?

I strongly believe that there are such examples, as otherwise $P = PSPACE$ (note that $P^{PSPACE} = PSPACE^{PSPACE}$), but I was looking for an example of this.

• Somewhat related questions: 1, 2 – Guilherme Rito Feb 28 '18 at 14:09
• So, essentially, you want $A,B$ such that $A\subsetneq B$ and take an oracle for $B$? Could we just take $A=P$ and $B=EXPTIME$? – Discrete lizard Feb 28 '18 at 15:42
• I don't think we can use $A = P$ and $B = EXPTIME$: the time hierarchy theorems relativize, and so that example does not work (i.e. there is no oracle $O$ such that $P^O = EXPTIME^O$). – Guilherme Rito Feb 28 '18 at 15:44
• @Discretelizard this question is related to the others I asked (and for which you contributed to). Although the question is not the same, the reason I am asking is, and this time I believe the question is formal. Right? – Guilherme Rito Feb 28 '18 at 16:15
• Ah yes, that obviously won't work easily as $EXPTIME^{EXPTIME}\neq EXPTIME$. Yes, now your question is sufficiently formal for it to be answerable. – Discrete lizard Feb 28 '18 at 18:25

Let $\mathsf{C}$ be a complexity class of your choice, let $\mathsf{O}$ be an oracle of your choice, and define $\mathsf{D} = \mathsf{C}^\mathsf{O}$. Then $\mathsf{C}^\mathsf{O} = \mathsf{D}^\mathsf{O}$, but it could happen that $\mathsf{C} \neq \mathsf{D}$. For example, you can take $\mathsf{C} = \mathsf{P}$ and $\mathsf{O} = \mathsf{HALT}$, the halting problem.
• I don't think your example works, because (1) $D=C^{O}$ does not imply $D^O=C^O$ even in your example and (2) $D$ is not in general a relativizable class. For (1): with $O=Halt$ we get $D=P^{Halt}$, so $D^O=P^{Halt^{Halt}}\ne P^{Halt}=C^O$. For (2): Take $O=Sparse$ and $D=P^{Sparse}$. What is $D^O$? It parses to $P^{Sparse^{Sparse}}$, but that makes little sense. – Lieuwe Vinkhuijzen Mar 1 '18 at 10:42
• The crux of the matter is that there is no "automatic" definition of relativized classes. For me, $D^O$ is what you get from $D$ by allowing it access to an $O$-oracle. For example, $(P^{Halt})^{Halt} = P^{Halt,Halt} = P^{Halt}$ (since access to both a Halt oracle and a Halt oracle is the same as access to a single Halt oracle). This is in the spirit of $(AC^0)^{Parity} = AC^0$. – Yuval Filmus Mar 1 '18 at 10:46
See Ryan Williams' answer here. An easy example is that $\mathsf{AC^0}\neq \mathsf{AC^0}$, but they are equal relative to a parity oracle.