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?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ The last paragraph of this answer suggests one possible consequence: cstheory.stackexchange.com/questions/3278/is-ph-subseteq-pp/… $\endgroup$– William WhistlerCommented Mar 16, 2015 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$– neophyteCommented Mar 17, 2015 at 1:23
-
6$\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$– ThatchapholCommented Mar 27, 2015 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 GrochowCommented Apr 19, 2017 at 20:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You could also ask similar questions about the polynomial hierarchy. The consensus in the research community is that PH is unlikely to collapse ... but I can't think of any dramatic consequences that would follow if Sigma^p_15 were closed under complement. There are many important implications of the form (PH infinite) implies (significant condition) ... but what follows from (PH collapses)? (This would imply that all unary languages accepted by uniform AC^0 circuits have uniform depth-k AC^0 circuits of quasipolynomial size ... but since the corresponding statement about uniform TC^0 (which would follow of CH collapses) doesn't seem to impress you, this statement about unary languages in uniform AC^0 probably doesn't impress you, either.)
I think it's reasonably likely that CH=PSPACE. I think that it's nearly as likely as CH being infinite. I think that it's very unlikely that CH has distinct levels up to, say, level 8, and then collapses. But I've been wrong before.
-- Eric
