Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top