Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  Niel de Beaudrap Nov 24 '12 at 13:26
    
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}$? –  Uriel Nov 24 '12 at 14:06
    
@Uriel: Usually, the reasons for motivations become clear after one has read a few theorems and proofs using them. –  Raphael Nov 24 '12 at 15:31
    
@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. –  Uriel Nov 24 '12 at 15:38
add comment

1 Answer

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

share|improve this answer
    
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? –  Uriel Nov 24 '12 at 20:47
    
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... –  Uriel Nov 25 '12 at 9:53
1  
@Uriel, use that along with subset relations between classes (eg, $\Sigma_i \subseteq \Pi_{i+1} \subseteq \Sigma_{i+2}$) –  Nicholas Mancuso Nov 26 '12 at 0:00
    
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? –  Uriel Nov 26 '12 at 14:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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