HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

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

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#88716, answer score: 11

Revisions (0)

No revisions yet.