# Is $PP^{(PP^A)} = PP^A$ ?

I've looked in the Zoo and it seems it is not true because $PH \subseteq P^{PP}$. Nonetheless I've passed by a paper that appears to have used a positive result. It was in the context that $f : \{0,1\}^* \mapsto \{0,1\}^*$ is a function, computable by probabilistic polynomial time oracle machine $M$ with access to an arbitrary oracle $A$. The authors say and I quote:

Its also immediate that $G^f$ ≡ $G^{M^A}$ is computable by a probabilistic polynomial time oracle machine with access to $A$.

where $G$ is a probabilistic polynomial time oracle machine.

They do it again also for $S^{N^A,M^A}$, $S,N$ being other probabilistic polynomial time oracle machine.

Update: the paper is "Notions of reducibility between cryptographic primitives" - 2004. It was in the proof of Lemma 1 of the part that "If there exists a fully-black-box reduction from a cryptographic primitive P to cryptographic primitive Q then there exists a relativizing reduction from P to Q as well." The definitions of fully-black-box and relativizing reduction is in the paper.

The question now, according to Lance Fortnow's answer that they are not equal, does that mean that this is a gap in the proof ?

• It might help if you tell us which paper you're quoting. – Robin Kothari Jun 18 '11 at 13:44
• @Robin Kothari: It is "Notions of reducibility between cryptographic primitives" - 2004 (springerlink.com/content/q3jp67gnpkhkn38q) – M. Alaggan Jun 18 '11 at 18:55

Richard Beigel gives an oracle $A$ where $P^{NP^A}\not\subseteq PP^A$ which immediately gives $PP^{PP^A}\neq PP^A$.