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$ – Watercrystal Jan 19 at 18:33
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 Jan 19 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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