Notations around the polynomial hierarchy

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$


Show:


$\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?

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

StackExchange Computer Science Q#6870, answer score: 2