3
$\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$
  • 3
    $\begingroup$ 1. Yes, this follows immediately from the fact that BPP is low for PP. $\endgroup$ – Emil Jeřábek May 6 '17 at 12:30
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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