<p>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.)</p>
<p>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.</p>
<p>-- Eric</p>

CC BY-SA 4.0
2021-11-23T23:17:11.047Z
2021-11-23T23:17:11.047Z
Eric Allender
<p>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?</p>

CC BY-SA 3.0
2015-03-16T19:30:09.500Z
The last paragraph of this answer suggests one possible consequence: http://cstheory.stackexchange.com/questions/3278/is-ph-subseteq-pp/3300#3300
William Whistler
CC BY-SA 3.0
2015-03-17T01:23:54.150Z
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.
neophyte
CC BY-SA 3.0
2015-03-27T23:59:45.723Z
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 http://eccc.hpi-web.de/keyword/18433/
Thatchaphol
CC BY-SA 3.0
2017-04-19T20:34:20.020Z
@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](http://dx.doi.org/10.4086/cjtcs.1999.007)), 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 https://cstheory.stackexchange.com/q/17978/129.) Doesn't answer your Q, but still seems a worthwhile comment.
Joshua Grochow
<cc.complexity-theory><counting-complexity><conditional-results><polynomial-hierarchy><pspace>
What are consequences of the collapse of CH?
neophyte
# What are consequences of the collapse of CH?

(Asked by: username_0 on 2015-03-15)

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?

**Tags:** cc.complexity-theory, counting-complexity, conditional-results, polynomial-hierarchy, pspace
> **Comments:**
> **username_1**: The last paragraph of this answer suggests one possible consequence: http://cstheory.stackexchange.com/questions/3278/is-ph-subseteq-pp/3300#3300  
> **username_0**: 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.  
> **username_2**: 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 http://eccc.hpi-web.de/keyword/18433/  
> **username_3**: @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](http://dx.doi.org/10.4086/cjtcs.1999.007)), 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 https://cstheory.stackexchange.com/q/17978/129.) Doesn't answer your Q, but still seems a worthwhile comment.  

---

## 1 answers

### Answer by username_4 on 2021-11-23. Score: 5

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


---

