2
$\begingroup$

Why does $\Pi_i^p \subseteq \Sigma_i^p$ imply $\Pi_i^p = \Sigma_i^p$?

$\endgroup$
1
$\begingroup$

Hint: $L \in \Sigma_i^p$ iff $\overline{L} \in \Pi_i^p$. (Here $\overline{L}$ is the complement of $L$.)

$\endgroup$
  • $\begingroup$ Well, this shows that $L \in \Sigma_i^p \text{iff} \bar{L} \in \Sigma_i^p$. And since by definition $\Pi_i^p = co\Sigma_i^p$, I guess it follows? (I was trying to show that $\Pi_i^p \subseteq \Sigma_i^p \implies \Sigma_i^p \subseteq \Pi_i^p$ but I couldn't do this. $\endgroup$ – ComplexityStudent Aug 12 '15 at 18:17
  • $\begingroup$ Keep thinking. You'll manage to solve this eventually. $\endgroup$ – Yuval Filmus Aug 12 '15 at 18:18
  • $\begingroup$ :D Okay! My approach is this : for some $x$ whose membership in $L \in \Sigma_i^p$ is being tested we have a decision predicate of the form $\exists y_1 .. Qy_i f(x,\vec{y})$ which is equivalent to its double negated form $\neg(\forall y_i .. \bar{Q} y_i \bar{f}(x,\vec{y}))$. But since $\Pi_i^p \subseteq \Sigma_i^p$ for a predicate like $\forall y_i .. \bar{Q} y_i \bar{f}(x,\vec{y})$ there exists an equivalent predicate like $\exists z_1.. Q z_i g(x,\vec{z})$ and then $\neg(\exists z_i .. Q z_i g(x,\vec{z}))$ is a predicate in $\Pi_i^p$. $\endgroup$ – ComplexityStudent Aug 12 '15 at 18:29
  • $\begingroup$ Yes, that's the idea, though it can be stated more succinctly. $\endgroup$ – Yuval Filmus Aug 12 '15 at 19:25

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.