0
$\begingroup$

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?

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

2 Answers 2

1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, but I still do not get it. I also edited my question accordingly. $\endgroup$
    – 3nondatur
    Nov 16, 2021 at 0:20
  • $\begingroup$ Thanks a lot for your help, I got it now. $\endgroup$
    – 3nondatur
    Nov 16, 2021 at 22:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.