7
$\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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Somewhat related questions: 1, 2 $\endgroup$
    – Guilherme Rito
    Feb 28, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 18:25

2 Answers 2

Reset to default
11
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 2018 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, 2018 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.

Improve this answer
$\endgroup$
0

Your Answer

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

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