snippetModerate
Can two different complexity classes be equal relative to an oracle? Example request
Viewed 0 times
canrelativeequalexamplerequestdifferenttwoclassesoraclecomplexity
Problem
Is there a known example of two complexity classes, $A$ and $B$, such that:
-
$A \neq B$;
-
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.
-
$A \neq B$;
-
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.
Solution
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.
This might seem like cheating, but it's exactly the same answer as the one by Willard Zhan.
Context
StackExchange Computer Science Q#88716, answer score: 11
Revisions (0)
No revisions yet.