2
$\begingroup$

My question related to relativized world. I would like to know about how to show that class is different from another class in the oracle world and whether this applied to our real world.

For example, let us have the following assumption: suppose for all oracles A we have $P^A \neq PSPACE^A$, then Does it imply that $P = PSPACE$?

$\endgroup$
1
  • 2
    $\begingroup$ Consider an "useless" oracle (say, $A = \emptyset$). $\endgroup$ Commented Jan 19, 2021 at 18:33

1 Answer 1

2
$\begingroup$

If $A = \emptyset$, or more generally, if $A \in \mathsf{P}$, then $\mathsf{P}^A = \mathsf{P}$ and $\mathsf{PSPACE}^A = \mathsf{PSPACE}$, and so $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ is the same as $\mathsf{P} \neq \mathsf{PSPACE}$.

It is also interesting to ask whether $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ for a random oracle implies $\mathsf{P} \neq \mathsf{PSPACE}$. This was disproved (with $\mathsf{P}$ replaced by $\mathsf{IP}$) by Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi in their paper The random oracle hypothesis is false.

$\endgroup$
1
  • $\begingroup$ Thank you so much Yuval! It is so interesting paper and some authors of that paper are Giant well-known in complexity community, it is worth reading. $\endgroup$
    – user777
    Commented Jan 19, 2021 at 20:14

Your Answer

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

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