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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.