Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$

Question

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}$.

Answer 1

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.