<p>The question appears to be related to the question of whether there exists an oracle relative to which the counting hierarchy <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#ch" rel="nofollow">CH</a> is infinite or not. This is an open problem according to the Zoo.</p>

CC BY-SA 3.0
2011-06-18T20:33:52.507Z
PP and PP^PP are only the first two levels of the hierarchy. It's not clear that an oracle that separates these two would also show that the entire hierarchy is infinite.
Robin Kothari
CC BY-SA 3.0
2011-06-18T22:45:29.990Z
Do you have any idea whether PP^(PP^A) is the same as (PP^PP)^A ?
Mohammad Alaggan
CC BY-SA 3.0
2011-06-18T14:17:35.810Z
2011-06-18T14:17:35.810Z
Martin Schwarz
<p>Richard Beigel <a href="http://www.springerlink.com/content/u57567564x383634/" rel="noreferrer">gives an oracle</a> $A$ where $P^{NP^A}\not\subseteq PP^A$ which immediately gives $PP^{PP^A}\neq PP^A$.</p>

CC BY-SA 3.0
2011-06-18T17:30:18.207Z
2011-06-18T17:30:18.207Z
Lance Fortnow
<p>I've looked in the <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pp">Zoo</a> 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: </p>

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

<p>where $G$ is a probabilistic polynomial time oracle machine.</p>

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

<p>Update: the paper is "<a href="http://springerlink.com/content/q3jp67gnpkhkn38q">Notions of reducibility between cryptographic primitives</a>" - 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. </p>

<p>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 ?</p>

CC BY-SA 3.0
2011-06-18T13:44:26.683Z
It might help if you tell us which paper you're quoting.
Robin Kothari
CC BY-SA 3.0
2011-06-18T18:55:35.220Z
@Robin Kothari: It is "Notions of reducibility between cryptographic primitives" - 2004 (http://www.springerlink.com/content/q3jp67gnpkhkn38q/)
Mohammad Alaggan
<cc.complexity-theory><complexity-classes><oracles>
Is $PP^{(PP^A)} = PP^A$ ?
Mohammad Alaggan
# Is $PP^{(PP^A)} = PP^A$ ?

(Asked by: username_0 on 2011-06-17)

I've looked in the [Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pp) 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](http://springerlink.com/content/q3jp67gnpkhkn38q)" - 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 ?

**Tags:** cc.complexity-theory, complexity-classes, oracles
> **Comments:**
> **username_1**: It might help if you tell us which paper you're quoting.  
> **username_0**: @Robin Kothari: It is "Notions of reducibility between cryptographic primitives" - 2004 (http://www.springerlink.com/content/q3jp67gnpkhkn38q/)  

---

## 2 answers

### Answer by username_3 on 2011-06-18. Score: 13 | Accepted answer

Richard Beigel [gives an oracle](http://www.springerlink.com/content/u57567564x383634/) $A$ where $P^{NP^A}\not\subseteq PP^A$ which immediately gives $PP^{PP^A}\neq PP^A$.


---

### Answer by username_2 on 2011-06-18. Score: 3

The question appears to be related to the question of whether there exists an oracle relative to which the counting hierarchy [CH](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#ch) is infinite or not. This is an open problem according to the Zoo.

> **Comments:**
> **username_1**: PP and PP^PP are only the first two levels of the hierarchy. It's not clear that an oracle that separates these two would also show that the entire hierarchy is infinite.  
> **username_0**: Do you have any idea whether PP^(PP^A) is the same as (PP^PP)^A ?  

---

