<p>The strongest result I know is that there is an oracle $A$ such that </p>

<blockquote>
  <p>$\text{RP}^A  \cap \text{co-RP}^A \nsubseteq \oplus\text{P}^A$</p>
</blockquote>

<p>This is stronger than an oracle separation between PSPACE and $\oplus$P (and NP and $\oplus$P).</p>

<p>This is Theorem 6 in the following paper:</p>

<blockquote>
  <p><a href="http://iopscience.iop.org/1468-4810/42/2/A02">N K Vereshchagin, RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS, Russian Acad. Sci. Izv. Math. 42 261 (1994)</a></p>
</blockquote>

<p>This paper is my go-to reference for all oracle separations. It has pretty much every oracle separation that we knew how to prove (as of 1994).</p>

CC BY-SA 3.0
2014-07-11T07:51:11.820Z
2014-07-11T07:51:11.820Z
Robin Kothari
<p>From the comment above: you can use the same oracle $A$ used in:</p>

<p><a href="http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf" rel="noreferrer">Richard Beigel, Harry Buhrman, and Lance Fortnow. 1998. NP might not be as easy as detecting unique solutions. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC '98).</a></p>

<p>for which $P^A= \oplus P^A  \neq NP^A = EXP^A$  ($EXP^A=NP^A\subseteq PSPACE^A$ also holds)</p>

CC BY-SA 3.0
2014-07-11T07:02:48.580Z
2014-07-11T07:02:48.580Z
Marzio De Biasi
<p>Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?</p>

CC BY-SA 3.0
2014-07-10T17:19:39.103Z
Perhaps you can use the same oracle $A$ used by [Fortnow et al., "NP might not be as easy as detecting unique solutions"](http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf) for which  $P^A = \oplus P^A$ and $\oplus P^A \supsetneq NP^A = EXP^A$ ($EXP^A = NP^A \subseteq PSPACE^A$ also holds)
Marzio De Biasi
CC BY-SA 3.0
2014-07-10T23:02:25.477Z
Thanks. Though I think $\supsetneq$ should be replaced with $\neq$ because $P \subseteq NP$ and this fact relativizes.
user2484
CC BY-SA 3.0
2014-07-11T02:11:49.103Z
@MarzioDeBiasi: Except for the issue with $\supsetneq$ pointed out by user672484, I think that should be an answer.
Joshua Grochow
<cc.complexity-theory><complexity-classes><counting-complexity>
Is there an oracle separating Parity-P from PSPACE?
user2484
# Is there an oracle separating Parity-P from PSPACE?

(Asked by: username_0 on 2014-07-10)

Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

> **Comments:**
> **username_1**: Perhaps you can use the same oracle $A$ used by [Fortnow et al., "NP might not be as easy as detecting unique solutions"](http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf) for which  $P^A = \oplus P^A$ and $\oplus P^A \supsetneq NP^A = EXP^A$ ($EXP^A = NP^A \subseteq PSPACE^A$ also holds)  
> **username_0**: Thanks. Though I think $\supsetneq$ should be replaced with $\neq$ because $P \subseteq NP$ and this fact relativizes.  
> **username_2**: @MarzioDeBiasi: Except for the issue with $\supsetneq$ pointed out by user672484, I think that should be an answer.  

---

## 2 answers

### Answer by username_3 on 2014-07-11. Score: 6 | Accepted answer

The strongest result I know is that there is an oracle $A$ such that

> $\text{RP}^A \cap \text{co-RP}^A \nsubseteq \oplus\text{P}^A$

This is stronger than an oracle separation between PSPACE and $\oplus$P (and NP and $\oplus$P).

This is Theorem 6 in the following paper:

> [N K Vereshchagin, RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS, Russian Acad. Sci. Izv. Math. 42 261 (1994)](http://iopscience.iop.org/1468-4810/42/2/A02)

This paper is my go-to reference for all oracle separations. It has pretty much every oracle separation that we knew how to prove (as of 1994).


---

### Answer by username_1 on 2014-07-11. Score: 6

From the comment above: you can use the same oracle $A$ used in:

[Richard Beigel, Harry Buhrman, and Lance Fortnow. 1998. NP might not be as easy as detecting unique solutions. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC '98).](http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf)

for which $P^A= \oplus P^A \neq NP^A = EXP^A$ ($EXP^A=NP^A\subseteq PSPACE^A$ also holds)


---

