4
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ 1. Yes, this follows immediately from the fact that BPP is low for PP. $\endgroup$ May 6, 2017 at 12:30

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is it possible $PP=BPP\implies PP=ZPP$ or is it unknown? $\endgroup$
    – Turbo
    Dec 6, 2020 at 21:37
  • 1
    $\begingroup$ @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 $\endgroup$ Dec 7, 2020 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.