<p>I don't know a reference, but I think both of these should be doable.</p>

<p>For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, and that thereby separates both $P^{A_1}$ and $NP^{A_1}$ from $PP^{A_1}$.  Then you want a second oracle (call it $A_2$) that encodes the solutions to all $PH^{A_1}$ problems, in a "staggered" fashion such that accessing the $k^{th}$ level of the hierarchy requires queries of size (say) $n^k$ (and hence you can only get a constant number of alternations in polynomial time).  This second oracle should cause $P^{A_1,A_2} = NP^{A_1,A_2} = PH^{A_1,A_2} = PH^{A_1}$.  (Note that $A_2$ is just an "outer" layer, meaning that any queries to $A_2$ can be simulated by $PH^{A_1}$ queries.)  Finally, you'll want to appeal to Yao's and Hastad's $AC^0$ lower bounds (i.e., the switching lemma) to show that a $PH^{A_1}$ machine <i>still</i> can't solve the $MAJORITY$ instances in $A_1$, and therefore $PP^{A_1}$ (and certainly $PP^{A_1,A_2} = PP^{PH^{A_1}}$) remains larger.</p>

<p>For your second oracle, you'll want to construct $B$ in such a way that you need to solve an $NP$ search problem in order to "unlock" a part of the oracle string that then boosts your power up to $PSPACE$.  (Here we exploit the fact that $NP^{PSPACE}$ and $PP^{PSPACE}$ are both $PSPACE$.)  A subtlety is that the secret part of the oracle can't just decide an unrelativized $PSPACE$-complete language: it also needs to provide the answers to $PSPACE$ computations that query $B$ itself.  Fortunately, it's known how to achieve that in stages, avoiding the circularity: basically, you encode the outputs of the $PSPACE^B$ machines that only query $B$ on inputs of size $p(n)$ or less, in a part of $B$ that requires queries of size $&gt;p(n)$ to access, and that's therefore "out of reach" for those machines (but not for <i>other</i> $PSPACE^B$ machines).  Meanwhile, the $P^B$ machines are left "completely in the dark" by all this.</p>

CC BY-SA 3.0
2013-03-30T19:23:50.803Z
2013-03-31T14:31:43.177Z
2013-03-31T14:31:43.177Z
Scott Aaronson
<p>I would like to know if there exists a relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where ${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$. </p>

CC BY-SA 3.0
2013-03-30T19:29:19.160Z
I have a blog post "extreme oracles" which has a list of oracle results from which many others follow, including the two you ask. http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html
Lance Fortnow
CC BY-SA 3.0
2013-03-30T19:34:33.030Z
@Lance: Damn, just saw that after posting my answer!  Well, maybe the OP will still find my "homemade" constructions useful.
Scott Aaronson
<cc.complexity-theory><oracles><relativization>
Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$
Tayfun Pay
# Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$

(Asked by: username_0 on 2013-03-30)

I would like to know if there exists a relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where ${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$.

**Tags:** cc.complexity-theory, oracles, relativization

> **Comments:**
> **username_1**: I have a blog post "extreme oracles" which has a list of oracle results from which many others follow, including the two you ask. http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html  
> **username_2**: @Lance: Damn, just saw that after posting my answer!  Well, maybe the OP will still find my "homemade" constructions useful.  

---

## 1 answers

### Answer by username_2 on 2013-03-30. Score: 14 | Accepted answer

I don't know a reference, but I think both of these should be doable.

For your first oracle: for starters you'll want an oracle (call it $A\_1$) that encodes exponentially-large $MAJORITY$ instances, and that thereby separates both $P^{A\_1}$ and $NP^{A\_1}$ from $PP^{A\_1}$. Then you want a second oracle (call it $A\_2$) that encodes the solutions to all $PH^{A\_1}$ problems, in a "staggered" fashion such that accessing the $k^{th}$ level of the hierarchy requires queries of size (say) $n^k$ (and hence you can only get a constant number of alternations in polynomial time). This second oracle should cause $P^{A\_1,A\_2} = NP^{A\_1,A\_2} = PH^{A\_1,A\_2} = PH^{A\_1}$. (Note that $A\_2$ is just an "outer" layer, meaning that any queries to $A\_2$ can be simulated by $PH^{A\_1}$ queries.) Finally, you'll want to appeal to Yao's and Hastad's $AC^0$ lower bounds (i.e., the switching lemma) to show that a $PH^{A\_1}$ machine *still* can't solve the $MAJORITY$ instances in $A\_1$, and therefore $PP^{A\_1}$ (and certainly $PP^{A\_1,A\_2} = PP^{PH^{A\_1}}$) remains larger.

For your second oracle, you'll want to construct $B$ in such a way that you need to solve an $NP$ search problem in order to "unlock" a part of the oracle string that then boosts your power up to $PSPACE$. (Here we exploit the fact that $NP^{PSPACE}$ and $PP^{PSPACE}$ are both $PSPACE$.) A subtlety is that the secret part of the oracle can't just decide an unrelativized $PSPACE$-complete language: it also needs to provide the answers to $PSPACE$ computations that query $B$ itself. Fortunately, it's known how to achieve that in stages, avoiding the circularity: basically, you encode the outputs of the $PSPACE^B$ machines that only query $B$ on inputs of size $p(n)$ or less, in a part of $B$ that requires queries of size $>p(n)$ to access, and that's therefore "out of reach" for those machines (but not for *other* $PSPACE^B$ machines). Meanwhile, the $P^B$ machines are left "completely in the dark" by all this.


---

