6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Somewhat related questions: 1, 2 $\endgroup$ – Guilherme Rito Feb 28 '18 at 14:09
  • $\begingroup$ 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$? $\endgroup$ – Discrete lizard Feb 28 '18 at 15:42
  • $\begingroup$ 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$). $\endgroup$ – Guilherme Rito Feb 28 '18 at 15:44
  • $\begingroup$ @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? $\endgroup$ – Guilherme Rito Feb 28 '18 at 16:15
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Feb 28 '18 at 18:25
10
$\begingroup$

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.

This might seem like cheating, but it's exactly the same answer as the one by Willard Zhan.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Lieuwe Vinkhuijzen Mar 1 '18 at 10:42
  • $\begingroup$ 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[2])^{Parity} = AC^0[2]$. $\endgroup$ – Yuval Filmus Mar 1 '18 at 10:46
8
$\begingroup$

See Ryan Williams' answer here. An easy example is that $\mathsf{AC^0}\neq \mathsf{AC^0[2]}$, but they are equal relative to a parity oracle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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