I am new to "Computational Complexity" and therefore I have enough problems with some exercises like the following one:

Remember: $\text{PH} := \bigcup_{i} \Sigma_i$


$\bullet \bigcup_{i}(\Sigma_i \cup \Pi_i \cup \Delta_i) = \bigcup_{i}\Sigma_i = \bigcup_{i}\Pi_i = \bigcup_{i}\Delta_i$

$\bullet \forall k \in \mathbb{N} (\Sigma_k = \Pi_k \Rightarrow \text{PH} = \Sigma_k)$

I have tried to make myself familiar with Polynomial hierarchy, but on the one hand I don't understand the meaning of the symbols $\Delta, \Sigma, \Pi$ and on the other hand I don't know how to solve the actual exercise.

Can somebody give me some help, please?

  • $\begingroup$ The symbols $\Sigma_k, \Pi_k, \Delta_k$ are just variable names, parameterized by an integer variable. They are sequences of sets, where the contents of each set are various languages (as after all a complexity class is a set of languages). If you replaced these labels with $A_k, B_k, C_k$, would it seem less mysterious when you look at the Wikipedia page? $\endgroup$ Nov 24, 2012 at 13:26
  • $\begingroup$ Thanks Niel for the clarification. Is there a reason for defining for example $\Sigma$ with $\Sigma_{i+1}^{\rm P} := \mbox{NP}^{\Sigma_i^{\rm P}}$ and why is $\Sigma_1^{\rm P} = {\rm NP}$? $\endgroup$
    – Uriel
    Nov 24, 2012 at 14:06
  • $\begingroup$ @Uriel: Usually, the reasons for motivations become clear after one has read a few theorems and proofs using them. $\endgroup$
    – Raphael
    Nov 24, 2012 at 15:31
  • $\begingroup$ @Raphael: Yes, that's true. This lecture is just an introductory one, so the problem is that although there is no time to introduce and explain all the specific details, we are expected to know them. So any help is still much appreciated. $\endgroup$
    – Uriel
    Nov 24, 2012 at 15:38

1 Answer 1


$\newcommand{\P}{\mathsf{P}}\newcommand{\PH}{\mathsf{PH}}$ $\newcommand{\SUM}[1]{\Sigma_{#1}^{\P}}\newcommand{\PROD}[1]{\Pi_{#1}^{\P}}$ $\newcommand{\DELTA}[1]{\Delta_{#1}^{\P}}$ $\newcommand{\NP}{\mathsf{NP}}\newcommand{\coNP}{\mathsf{coNP}}$ From the comments:

Why is $\SUM{1} = \NP$?

Recall the definition of $\NP$ using certificates/proofs:

A language $L$ is in $\NP$ if there exists a poly-time TM $M$ and a polynomial $q$ such that $$x \in L \iff \exists u \in \{0,1\}^{q(|x|)}\ M(x, u) = 1$$

This is also exactly the definition for $\SUM{1}$. In the case of $\NP$ it is a single existential ($\exists$) quantifier. Now, the negation of existential quantifier is the universal quantifier ($\forall$). If we swap out the quantifiers in the certificate definition of $\NP$ we have $$x \in L \iff \forall u \in \{0,1\}^{q(|x|)}\ M(x, u) = 1$$ which is exactly $\coNP$ (and denoted in the hierarchy as $\PROD{1}$)! We see that $\PH$ is just a generalization of this, by allowing more (alternating) quantifiers.

For the first bullet:

$\bigcup_{i}(\SUM{i} \cup \PROD{i} \cup \DELTA{i}) = \bigcup_{i}\SUM{i} = \bigcup_{i}\PROD{i} = \bigcup_{i}\DELTA{i}$

Sketch: It is straightforward to show that $\SUM{i} \subseteq \PROD{i+1} \subseteq \SUM{i+2}$. The reasoning is that you can simply "ignore" the leading quantifiers in the verifying TM. Likewise, we see $\SUM{i} \subseteq \DELTA{i+1} \subseteq \SUM{i+1}$. Again, this can be explained due to the fact that both $\DELTA{i+1}$ and $\SUM{i+1}$ have oracle access to $\SUM{i}$ with the difference being that $\SUM{i+1}$ is an $\NP$-based machine whereas $\DELTA{i+1}$ is a $\P$-based machine.

With the subset relation in-hand, we see that a union over all integers will cover all cases.

Now for your second bullet:

$\forall k \in \mathbb{N}\ \ \SUM{k} = \PROD{k} \Rightarrow \PH = \SUM{k}$

Proof: This can be shown by induction on $k$. For our base case let $k = 1$ and observe that if $\SUM{1} = \PROD{1}$ then a collapse occurs. To see this, let $Q_1, \cdots, Q_i$ be the alternating quantifiers for some level $i$ in the hierarchy. Since $\SUM{1} = \PROD{1}$, we can replace each universal quantifier in the sequence with an existential quantifier resulting in $\exists u_1, \cdots, \exists u_i$. But by definition of the quantifiers, we can reduce this to a single $\exists \langle u_1, \cdots, u_i \rangle$ which is exactly $\SUM{1}$.

Now assume this holds for all values less than $k$. Given level $\SUM{k}$ we can decompose its quantifiers into two parts, the initial $\exists u_1$ and the following alternating sequence $\forall u_2, \cdots, Q_{k} u_{k}$, where $Q_{k}$ is either $\exists$ or $\forall$ depending on whether $k$ is odd or even. Observe this sequence is exactly $\PROD{k-1}$ which by our hypothesis is equal to $\SUM{k-1}$. By substituting and combining the initial term we have $$\exists \langle u_1, u_2 \rangle, \cdots, Q_{k} u_{k}$$ which is really only $k-1$ terms! Therefore a collapse occurs.

  • $\begingroup$ Thank you for your answer, Nicholas. The first bullet is probably easy, but I guess I'm too blind to see what does the trick. Do I need induction again? I saw that in the second bullet you've changed $Σ_k \subseteq Π_k$ to $Σ_k = Π_k$ and I don't know why. Can you please explain that? $\endgroup$
    – Uriel
    Nov 24, 2012 at 20:47
  • $\begingroup$ I'll then try to solve the first bullet with induction as preparation for the second bullet. Base case $i=0$: $\bigcup_{0}(\Sigma_0 \cup \Pi_0 \cup \Delta_0) = \bigcup_{0}\Sigma_0 = \bigcup_{0}\Pi_0 = \bigcup_{0}\Delta_0$ clear, because $\Sigma_0 = \Delta_0 = \Pi_0 = P$. Case $i = i+1$: Now I am really wondering how to go on... $\endgroup$
    – Uriel
    Nov 25, 2012 at 9:53
  • 1
    $\begingroup$ @Uriel, use that along with subset relations between classes (eg, $\Sigma_i \subseteq \Pi_{i+1} \subseteq \Sigma_{i+2}$) $\endgroup$ Nov 26, 2012 at 0:00
  • $\begingroup$ I am mortally embarrassed but I really can't provide any further own approach than the above. I've never had any problems with induction in "Calculus 1 for Computer Science", but here I'm blind. Can you please show at least a little bit of the further solution? $\endgroup$
    – Uriel
    Nov 26, 2012 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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