Are there two kinds of polynomial hierarchy collapses?

Question

It seems to me that there are two different situations which get called ``PH collapse",

(1) That $\exists i \geq 1$ s.t $\Sigma_i ^p = \Sigma_{i+1}^p$
(2) That $\exists i \geq 1$ s.t $\Sigma_i^p = \Pi_i^p$

• Are these two different independent situations?

---

AFAIK the only natural relation is that $\Sigma_i^p \subseteq \Pi_{i+1}^p \subseteq \Sigma_{i+2}^p$ and I don't think this is enough to make the two above scenarios be equivalent.

• Is there any natural relation even between $\Sigma_i^p$ and $\Sigma_{i+1}^p$ or between $\Pi_i^p$ and $\Pi_{i+1}^p$? For some $k > i$, if one shows that $\Sigma_k^p \subseteq \Sigma_i^p$ does that say anything about $\Pi_k^p$ vs $\Sigma_i^p$ ?

---

• Do both these scenarios lead to the conclusion that $PH = \cup _{j \geq 1} \Sigma_j^p = \Sigma_i ^p$ ? (If yes, then can someone kindly help with the proof?)

---

Roughly I guess the proof has to go like this :

That inductively assume that for some $k > i$ one has shown that $\Sigma_j^p \subseteq \Sigma_i^p$ $\forall j$ s.t $i\leq j \leq k$. Now sit at the threshold of the inductive hypothesis — and take some $L \in \Sigma_{k+1}^p$ and by truncating the first quantifier construct a language $L'$ such that $\langle x,u_1\rangle \in L'$ iff $x \in \Sigma_{k+1}^p$ with its first existential quantifier fixed to $u_1$. This makes $L' \in \Pi_{k}^p$

Now I don't know... something needs to be claimed about $L' \in \Pi_{k}^p$ to show that $L \in \Sigma_i^p$. But I don't see what goes here.

Answer 1

Suppose that $\Sigma_i^p = \Sigma_{i+1}^p$ (and so $\Pi_i^p = \Pi_{i+1}^p$). Then every statement of the form $(\exists y_1) \cdots (Q y_{i+1}) f(x,\vec{y})$ for polytime $f$ is equivalent to another statement $(\exists y_1) \cdots (Q y_i) g(x,\vec{y})$ for polytime $g$.

Now suppose you have a predicate in $\Sigma_{i+2}^p$, say $(\exists y) (\forall z_1) \cdots (Q z_{i+1}) f(x,y,\vec{z})$. The inner $i+1$ quantifiers are a $\Pi_{i+1}^p$ predicate, and so they are equivalent to a $\Pi_i^p$ predicate $(\forall z_1) \cdots (Q z_i) g(x,y,\vec{z})$. Adding back the outer quantifier $(\exists y)$, we find that the original predicate is equivalent to a $\Sigma_{i+1}^p$ predicate, and so $\Sigma_{i+2}^p = \Sigma_{i+1}^p = \Sigma_i^p$.

In the same way, we show that $\Sigma_i^p = \Sigma_{i+1}^p$ implies $\Sigma_i^p = \Sigma_{i+j}^p$ for all $j$, so that $\mathsf{PH} = \Sigma_i^p$.

Note that $\Pi_i^p \subseteq \Sigma_{i+1}^p$. Indeed, if $(\forall y_1) \cdots (Q y_i) f(x,\vec{y})$ is a $\Pi_i^p$ predicate, then the equivalent $(\exists w) (\forall y_1) \cdots (Q y_i) f(x,\vec{y})$ is a $\Sigma_{i+1}^p$ predicate.

Since $\Pi_i^p \subseteq \Sigma_{i+1}^p$, we see that $\Sigma_i^p = \Sigma_{i+1}^p$ implies that $\Pi_i^p \subseteq \Sigma_i^p$ and so $\Pi_i^p = \Sigma_i^p$.

---

Now for the other direction. Suppose that $\Pi_i^p = \Sigma_i^p$, and consider some $\Sigma_{i+1}^p$ predicate $(\exists y_1) (\forall y_2) \cdots (Q y_{i+1}) f(x,\vec{y})$. The inner $i$ quantifiers are a $\Pi_i^p$ predicate, and so they are equivalent to some $\Sigma_i^p$ predicate $(\exists z_2) \cdots (Q z_{i+1}) g(x,\vec{y})$. Adding back the outer quantifier $(\exists y_1)$ and folding $y_1,z_2$, we obtain a $\Sigma_i^p$ predicate equivalent to our original $\Sigma_{i+1}^p$ predicate.

Summarizing, if $\Pi_i^p = \Sigma_i^p$ then $\Sigma_i^p = \Sigma_{i+1}^p$, and so (as we have seen above) $\mathsf{PH} = \Sigma_i^p$.