Can two different complexity classes be equal relative to an oracle? Example request
-
05-11-2019 - |
Pergunta
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.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange