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

Question

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?

Answer 1

Hint 1: Substitute directly into the definition of the hierarchy with oracles. Use induction in the proof.

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)

Answer 2

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.