If you want to make money online : Register now

[Solved]: What is an oracle separating IP and PSPACE?

, , No Comments
Problem Detail: 

I saw this link on cstheory:

http://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.

Asked By : Ari

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28508

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback