1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: Use the definitions of $\Sigma_i^p,\Pi_i^p$. $\endgroup$ – Yuval Filmus May 9 '15 at 0:47
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks! Is there a typo in your last line? So what is the answer to my first and the second bullet point? $\endgroup$ – user6818 May 9 '15 at 0:57
  • $\begingroup$ Thanks for the correction. As I attempted to show, if either $\Sigma_i^p = \Sigma_{i+1}^p$ or $\Sigma_i^p = \Pi_i^p$ then $\mathsf{PH} = \Sigma_i^p = \Pi_i^p$. The rest of your questions I think you can answer on your own now. $\endgroup$ – Yuval Filmus May 9 '15 at 0:58
  • $\begingroup$ And so the proof idea that I was trying to sketch - was that totally off track? $\endgroup$ – user6818 May 9 '15 at 1:13
  • $\begingroup$ You tell me. I haven't read it myself. $\endgroup$ – Yuval Filmus May 9 '15 at 1:26

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.