<p>What are some examples of theorems of the form "If <span class="math-container">$X$</span>, then <span class="math-container">$PH$</span> collapses", but where the proof does not say which level <span class="math-container">$PH$</span> collapses to?  </p>

<p>The canonical example would be "If <span class="math-container">$PH = PSPACE$</span>, then <span class="math-container">$PH$</span> collapses", though this one is trivial.  Are there more interesting examples?</p>

CC BY-SA 4.0
2019-06-20T00:51:40.273Z
I think your last example has little to do with PSPACE being an "adaptive union of the levels of PH": the same holds for any class C which has a complete problem and contains PH (and just assuming C in PH, but I think that's what you meant anyway).
Joshua Grochow
CC BY-SA 4.0
2019-06-20T03:04:26.197Z
@JoshuaGrochow: Yep, that's fair.
Geoffrey Irving
CC BY-SA 4.0
2019-06-20T04:40:04.143Z
Your example does not fit the criterion, it seems. If P=PSPACE then PH collapses to its 0th level.
Ryan Williams
CC BY-SA 4.0
2019-06-20T05:13:05.733Z
@RyanWilliams: I think he meant if PSPACE is in PH (then we know it collapses, but not to which level).
Joshua Grochow
CC BY-SA 4.0
2019-06-20T05:37:56.263Z
It's easy to construct trivial examples. One that's probably not obvious (without knowing Toda's theorem) is that $\mathrm{PP} \subseteq \mathrm{PH}$ implies the collapse of $\mathrm{PH}$. But this is only "technically" true, as knowing where in the hierarchy $\mathrm{PP}$ lies will give you a pretty good estimate for where $\mathrm{PH}$ collapses.
Yonatan N
CC BY-SA 4.0
2019-06-20T06:32:35.573Z
Yep, I meant $PH = PSPACE$.  Fixed.
Geoffrey Irving
<big-list><polynomial-hierarchy>
Examples of ineffective PH collapse theorems?
Geoffrey Irving
# Examples of ineffective PH collapse theorems?

(Asked by: username_0 on 2019-06-19)

What are some examples of theorems of the form "If $X$, then $PH$ collapses", but where the proof does not say which level $PH$ collapses to?

The canonical example would be "If $PH = PSPACE$, then $PH$ collapses", though this one is trivial. Are there more interesting examples?

**Tags:** big-list, polynomial-hierarchy

> **Comments:**
> **username_1**: I think your last example has little to do with PSPACE being an "adaptive union of the levels of PH": the same holds for any class C which has a complete problem and contains PH (and just assuming C in PH, but I think that's what you meant anyway).  
> **username_0**: @JoshuaGrochow: Yep, that's fair.  
> **username_2**: Your example does not fit the criterion, it seems. If P=PSPACE then PH collapses to its 0th level.  
> **username_1**: @RyanWilliams: I think he meant if PSPACE is in PH (then we know it collapses, but not to which level).  
> **username_3**: It's easy to construct trivial examples. One that's probably not obvious (without knowing Toda's theorem) is that $\mathrm{PP} \subseteq \mathrm{PH}$ implies the collapse of $\mathrm{PH}$. But this is only "technically" true, as knowing where in the hierarchy $\mathrm{PP}$ lies will give you a pretty good estimate for where $\mathrm{PH}$ collapses.  
> **username_0**: Yep, I meant $PH = PSPACE$.  Fixed.  

---

## 0 answers

