0
$\begingroup$

I saw this link on cstheory:

https://cstheory.stackexchange.com/questions/6634/is-there-an-oracle-that-separates-two-complexity-classes-known-to-be-equal

but it did not provide specific details. Can anyone tell me what the specific oracle is (or direct me to a paper which does)? Also on a meta-level why does this not call into question the legitimacy of oracle Turing machines- if two classes coincide, how can they be separated? Thanks.

$\endgroup$
2
$\begingroup$

The answer to the question you link contains all the information you need. The multi-authored paper The random oracle hypothesis is false proves the stronger result that IP and PSPACE are different with probability 1 with respect to a random oracle. They also comment that a concrete oracle under which IP differs from PSPACE can be constructed using standard techniques, by which they mean the form of diagonalization used to separate P from NP with respect to a concrete oracle; they do not provide any details, though. Presumably it is a not too difficult exercise.

The meta-question is addressed both in the answer you link and in the paper. I suggest you first read the paper, and then if you have more questions, you can ask them here in this site.

$\endgroup$
  • $\begingroup$ Thanks. Sorry I guess I should have read the post more carefully. $\endgroup$ – Ari Jul 18 '14 at 3:27

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.