6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Perhaps you can use the same oracle $A$ used by Fortnow et al., "NP might not be as easy as detecting unique solutions" 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) $\endgroup$ – Marzio De Biasi Jul 10 '14 at 17:19
  • 1
    $\begingroup$ Thanks. Though I think $\supsetneq$ should be replaced with $\neq$ because $P \subseteq NP$ and this fact relativizes. $\endgroup$ – user2484 Jul 10 '14 at 23:02
  • 1
    $\begingroup$ @MarzioDeBiasi: Except for the issue with $\supsetneq$ pointed out by user672484, I think that should be an answer. $\endgroup$ – Joshua Grochow Jul 11 '14 at 2:11
6
$\begingroup$

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)

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).

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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).

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

| cite | improve this answer | |
$\endgroup$

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.