7
$\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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Then it means $P\ne NP$, otherwise, how can an oracle separate them? $\endgroup$
    – pyao
    Commented May 18, 2011 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
    Commented May 18, 2011 at 12:27
  • $\begingroup$ I suggest that you change the question to reflect this. $\endgroup$
    – Dave Clarke
    Commented May 18, 2011 at 13:21
  • 1
    $\begingroup$ related: 1 $\endgroup$
    – Kaveh
    Commented May 19, 2011 at 6:07

1 Answer 1

Reset to default
20
$\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.

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ i.e. relativization is not defined for languages but for specific machines and depends on the structure of the machine. :) $\endgroup$
    – Kaveh
    Commented May 19, 2011 at 6:15

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.