# If $\Sigma_i^P = \Sigma_{i+1}^P$ then for all $k \ge i$ holds $\Sigma_k^P = \Sigma_{k+1}^P$

I am struggling with the following remark from lecture:

Suppose the Polynomial Hierarchy collapses at the $$i$$-th level, i.e. $$\Sigma_i^P = \Sigma_{i+1}^P$$. Then for all $$k \ge i$$ holds $$\Sigma_k^P = \Sigma_{k+1}^P$$.

The only similar relation I know of is $$\Sigma_i^P \subseteq \Pi_{i+1}^P \subseteq \Sigma_{i+2}^P$$ holds, but I do not understand see how this could help here. I have also tried to use induction, but it lead to nowhere. Could you please give me a hint?

Following nir shahar's answer I now have the following:

We aim to proof this claim by induction:

• Induction Basis: $$\Sigma_i^P = \Sigma_{i+1}^P$$
• Induction Hypothesis: $$\Sigma_{k-1}^P = \Sigma_{k}^P$$ for some $$k \ge i$$.
• Induction Step: We want to show that $$\Sigma_k^P = \Sigma_{k+1}^P$$.

Following nir shahar's answer I tried to use the oracle definition of the polynomial hierarchy, so $$\Sigma_k^P = NP^{\Sigma_{k-1}SAT}$$ and $$\Sigma_{k+1}^P = NP^{\Sigma_{k}SAT}$$.

Remark: We defined $$\Sigma_{i}SAT$$ as the set of formulas $$\phi$$ such that

$$\phi \exists y_1\forall y_2 \ldots Q_i \phi(y_i,\ldots,y_k)$$

, where $$Q_i = \exists$$ if $$2 \nmid j$$ and $$Q_i = \forall$$ if $$2 \mid j$$.

However, I just do not understand why these two should be equal. Could you please give me a another hint?

• Another hint: you can prove that for all $k\geqslant i$, $\Sigma_k^P = \Sigma_i^P$. Nov 16, 2021 at 10:07

Hint 2: It is well known that $$\Sigma_kSAT=\Sigma_k^P$$. Try to use this in your proof (make sure you learned this in class! Its an important theorem)
Hint: Try to reduce the quantified boolean statement to an equivalent one in $$\Sigma_k SAT$$. This should establish the subset relationship which can be used to argue for equality of the two classes.