<p>Yes, the counting hierarchy collapses in this case: Suppose that $P^{\#P}\subseteq BPP$. We know that $P^{\#P}=P^{PP}$, so $P^{PP}\subseteq BPP$. Consider the second level of the counting hierarchy, $C_2^P=PP^{PP}$. By hypothesis, we have</p>

<p>$$C_2^P=PP^{PP}\subseteq PP^{P^{PP}}\subseteq PP^{BPP}\subseteq PP\subseteq P^{PP}\subseteq BPP $$</p>

<p>So the counting hierarchy collapses to $BPP$.</p>

<p>As for your second question, I don't know any implications that would follow from a weaker collapse of the counting hierarchy, i.e. $CH=PP$ or something weaker. That question has been asked before, <a href="https://cstheory.stackexchange.com/q/30816/35749">here</a>, without answers. <a href="https://cstheory.stackexchange.com/q/3278/35749">This question</a> asks whether $PH\subseteq PP$; but nothing more would necessarily follow if $CH$ collapses, even under that hypothesis. According to <a href="https://cstheory.stackexchange.com/a/4691/35749">this answer</a>, it is an open problem whether $PH^{\#P}$ collapses (note that $PH^{\#P}$ does <em>not</em> trivially collapse as a result of Toda's theorem).</p>

<p>There are at present, according to the <a href="https://www.math.ucdavis.edu/~greg/zoology/diagram.xml" rel="noreferrer">Zoology active inclusion diagram</a>, no oracles relative to which the counting hierarchy collapses to <em>any</em> level other than $CH=P^{\#P}$; that is, it is an open problem to find an oracle relative to which $P^{\#P}\subsetneq CH$ or indeed $P^{\#P}\subsetneq PSPACE$. Hence there are no oracles, therefore, supporting any argument relating non-trivial collapses of the counting hierarchy to the polynomial hierarchy.</p>

CC BY-SA 4.0
2020-12-06T21:37:07.240Z
Is it possible $PP=BPP\implies PP=ZPP$ or is it unknown?
Turbo
CC BY-SA 4.0
2020-12-07T20:14:17.273Z
@1.. Good question. As far as I know, this is unknown. My gut feeling is that there is an oracle such that $ZPP\subsetneq BPP=PP$, and that therefore, if the implication holds at all, then it requires non-relativizing techniques. If I come up with such an oracle, or find one, then I'll come back to this comment
Lieuwe Vinkhuijzen
CC BY-SA 3.0
2017-05-08T12:12:24.277Z
2017-05-08T12:12:24.277Z
Lieuwe Vinkhuijzen
<p>Supposing if $P^{\#P}\subseteq BPP$ then polynomial hierarchy collapses. </p>

<ol>
<li><p>Does the counting hierarchy collapse as well?</p></li>
<li><p>Irrespective of $P^{\#P}\subseteq BPP$ are there any collapse results of counting hierarchy that imply collapse results of polynomial hierarchy and vice versa?</p></li>
</ol>

CC BY-SA 3.0
2017-05-06T12:30:47.600Z
1. Yes, this follows immediately from the fact that BPP is low for PP.
Emil Jeřábek
<counting-complexity><polynomial-hierarchy>
Where is the counting hierarchy if polynomial hierarchy collapses?
QQQ
# Where is the counting hierarchy if polynomial hierarchy collapses?

(Asked by: username_0 on 2017-05-06)

Supposing if $P^{\#P}\subseteq BPP$ then polynomial hierarchy collapses.

1. Does the counting hierarchy collapse as well?
2. Irrespective of $P^{\#P}\subseteq BPP$ are there any collapse results of counting hierarchy that imply collapse results of polynomial hierarchy and vice versa?

**Tags:** counting-complexity, polynomial-hierarchy

> **Comments:**
> **username_1**: 1. Yes, this follows immediately from the fact that BPP is low for PP.  

---

## 1 answers

### Answer by username_2 on 2017-05-08. Score: 5

Yes, the counting hierarchy collapses in this case: Suppose that $P^{\#P}\subseteq BPP$. We know that $P^{\#P}=P^{PP}$, so $P^{PP}\subseteq BPP$. Consider the second level of the counting hierarchy, $C\_2^P=PP^{PP}$. By hypothesis, we have

$$C\_2^P=PP^{PP}\subseteq PP^{P^{PP}}\subseteq PP^{BPP}\subseteq PP\subseteq P^{PP}\subseteq BPP $$

So the counting hierarchy collapses to $BPP$.

As for your second question, I don't know any implications that would follow from a weaker collapse of the counting hierarchy, i.e. $CH=PP$ or something weaker. That question has been asked before, [here](https://cstheory.stackexchange.com/q/30816/35749), without answers. [This question](https://cstheory.stackexchange.com/q/3278/35749) asks whether $PH\subseteq PP$; but nothing more would necessarily follow if $CH$ collapses, even under that hypothesis. According to [this answer](https://cstheory.stackexchange.com/a/4691/35749), it is an open problem whether $PH^{\#P}$ collapses (note that $PH^{\#P}$ does *not* trivially collapse as a result of Toda's theorem).

There are at present, according to the [Zoology active inclusion diagram](https://www.math.ucdavis.edu/~greg/zoology/diagram.xml), no oracles relative to which the counting hierarchy collapses to *any* level other than $CH=P^{\#P}$; that is, it is an open problem to find an oracle relative to which $P^{\#P}\subsetneq CH$ or indeed $P^{\#P}\subsetneq PSPACE$. Hence there are no oracles, therefore, supporting any argument relating non-trivial collapses of the counting hierarchy to the polynomial hierarchy.

> **Comments:**
> **username_3**: Is it possible $PP=BPP\implies PP=ZPP$ or is it unknown?  
> **username_2**: @1.. Good question. As far as I know, this is unknown. My gut feeling is that there is an oracle such that $ZPP\subsetneq BPP=PP$, and that therefore, if the implication holds at all, then it requires non-relativizing techniques. If I come up with such an oracle, or find one, then I'll come back to this comment  

---

