# Where is the counting hierarchy if polynomial hierarchy collapses?

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?

• 1. Yes, this follows immediately from the fact that BPP is low for PP. – Emil Jeřábek May 6 '17 at 12:30

## 1 Answer

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, without answers. This question asks whether $PH\subseteq PP$; but nothing more would necessarily follow if $CH$ collapses, even under that hypothesis. According to this answer, 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, 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.