I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important consequences of the collapse of $CH$? I got a sort of intuition behind the conjecture the polynomial hierarchy $PH$ doesn't collapse. Nevertheless, since $PP^{PH}\subseteq P^{PP}=P^{\# P}\subseteq C_2^P$ due to the Toda's theorem, where $C_2^P$ is the second level of $CH$, the power of counting seems huge. Thus, what would be wrong or unexpected if $CH$ collapsed? And what if the stronger condition $CH=PSPACE$ held?

  • 2
    $\begingroup$ The last paragraph of this answer suggests one possible consequence: cstheory.stackexchange.com/questions/3278/is-ph-subseteq-pp/… $\endgroup$ – William Whistler Mar 16 '15 at 19:30
  • 3
    $\begingroup$ It does not. The answer you quoted says that the collapse of CH is closely related to another problem with constant-depth threshold circuits. But it does not clarify the relation. According to the complexity zoo $TC^0=CN^1$ imples $CH=PSPACE$ which in turn implies the collapse of $CH$. Thus, constant-depth threshold circuits provide a sufficient condition for the collapse of $CH$, not a consequence. $\endgroup$ – neophyte Mar 17 '15 at 1:23
  • 5
    $\begingroup$ There some problems, like $BitSLP$ and $PosSLP$, whose best known complexity is in the high-level hierarchy of $CH$. The collapse of $CH$ would trivially improve their complexity. See eccc.hpi-web.de/keyword/18433 $\endgroup$ – Thatchaphol Mar 27 '15 at 23:59
  • $\begingroup$ @neophyte: While the padding argument only goes one way, there's still the feeling that the fates of $TC^0$ and $CH$ are closely intertwined; viz., there's a nondet. model (Allender), for which uniform-$TC^0$=logtime in that model and CH=polytime in that model. If CH were to collapse, my Bayesian posterior on the $TC^0$ depth hierarchy collapsing would increase dramatically, though we do not know a formal implication to this effect. (See also cstheory.stackexchange.com/q/17978/129.) Doesn't answer your Q, but still seems a worthwhile comment. $\endgroup$ – Joshua Grochow Apr 19 '17 at 20:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.