5
$\begingroup$

We know that there exist two oracles $A$ and $B$ such that $P^A=NP^A$ and $P^B\neq NP^B$, this implies the obstacle of proving $P\neq NP$ using diagonalization. I just wonder if there exist two complexity classes, say $A$ and $B$ and oracle $O$ such that $A=B$ but $A^O\neq B^O$?

I am not sure if it is a research-level problem. So don't hesitate to close it if not.

Thanks.

$\endgroup$
  • 2
    $\begingroup$ Then it means $P\ne NP$, otherwise, how can an oracle separate them? $\endgroup$ – pyao May 18 '11 at 12:26
  • $\begingroup$ OK, here "the same" means they are shown to be same, but may use completely different definitions, like $IP=PSPACE$. $\endgroup$ – pyao May 18 '11 at 12:27
  • $\begingroup$ I suggest that you change the question to reflect this. $\endgroup$ – Dave Clarke May 18 '11 at 13:21
  • 1
    $\begingroup$ related: 1 $\endgroup$ – Kaveh May 19 '11 at 6:07
17
$\begingroup$

We have IP = PSPACE = PPSPACE, where PPSPACE is the "probabilistic polynomial space," as defined by Papadimitriou's Games Against Nature.

However, relative to a random oracle O, we have IPO ≠ PSPACEO = PPSPACEO with probability 1. (See The Random Oracle Hypothesis is False.)

Another example: let the assumption be false; that is, if A=B the AO = BO for any oracle O and all complexity classes A and B. The contrapositive will say: If AO ≠ BO, then A ≠ B. Specially, since there exists an oracle O such that PO ≠ NPO, then P ≠ N, and a long-standing problem is solved!!!

Obviously, this reasoning has no basis, and I believe it can be refuted as such.

PS: When we use the "=" sign with respect to sets, we mean that every element of one set is also a member of the other set, and vice versa. However, the sets might have totally different definitions. In the axiomatic set theory, this is called the axiom of extensionality. The reason of "IP = PSPACE but IPO ≠ PSPACEO with probability 1 for a random oracle O" is exactly this: While IP and PSPACE are externally identical, their internal structure is quite different.

$\endgroup$
  • 7
    $\begingroup$ i.e. relativization is not defined for languages but for specific machines and depends on the structure of the machine. :) $\endgroup$ – Kaveh May 19 '11 at 6:15

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.