# Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $$S_2$$ is closed under union and complement, even though in this Wikipedia article it says that:

It is immediate from the definition that $$S_2$$ is closed under union and complement.

I think that my problem is due to the fact that $$S_2$$ is defined slightly differently in my assignment. Here's the definition I must work with:

$$S_2$$ is the complexity class of all languages $$L$$ for which there exists a polynomial bound verifier $$V$$ and a polynomial $$p$$ such that for all $$x \in \{0,1\}^*$$:

$$x \in L \Rightarrow \exists y \in \{0,1\}^{p(|x|)} \forall z \in \{0,1\}^{p(|x|)} : V(x,y,z)=1$$ $$x \notin L \Rightarrow \exists z \in \{0,1\}^{p(|x|)} \forall y \in \{0,1\}^{p(|x|)} : V(x,y,z)=0$$

Let's look first at union. Let $$A,B \in S_2$$. I thought of defining a new verifier $$V_{A \cup B} = V_A \lor V_B$$ which should return a correct answer. However, my problem is defining the new polynomial $$p$$. Let's say that the polynomials that exist for languages $$A,B$$ are $$p_A,p_B$$ and that $$p_A < p_B$$. Now let's look at some $$x \in A \cup B$$.

The problem is that if $$x \in A$$ all I know is that there exists a $$y$$ s.t. $$|y|=p_A(|x|)$$ and that if $$x \in B$$ there exists a $$y$$ s.t. $$|y|=p_B(|x|)$$. But how do I define a polynomial $$q$$ such that I can be sure that there exists a $$y$$ s.t. $$|y|=q(|x|)$$ for any general $$x$$?

As for the closure under complement, if $$A \in S_2$$, all I know is that if $$x \in \overline A$$, then $$x \notin A$$, therefore $$\exists z \in \{0,1\}^{p(|x|)} \forall y \in \{0,1\}^{p(|x|)} : V(x,y,z)=0$$. However I do not see how we use this in order to conclude that $$\exists y \in \{0,1\}^{p(|x|)} \forall z \in \{0,1\}^{p(|x|)} : V(x,y,z)=1$$.

As you mention in your post, you can define a new verifier $V=V_A \vee V_B$ however, you missed the point that the input of $V$ need not be the input of $V_A$ or $V_B$: it can be the concatenation of their inputs
So the new $V$ can be written as $$V(x, y_A\circ y_B, z_A \circ z_B )$$ where it "runs" $V_A(x,y_A,z_A)$ and $V_A(x,y_B,z_B)$ and decides accordingly.
It then immediately follows that $q = p_a +p_b +1$ (the +1 is just to separate the prefix from the suffix, you can ignore it).
• Oh, I see you asked two independent questions in the same post. Try to avoid that. As for the answer of the second part: can't you just take for the compliment the verifier $V_{comp}= V(x,z,y)$ and flip the answer? – Ran G. Jun 16 '15 at 22:26
• Thanks @Ran G. but two things aren't clear to me: 1) In the concatenation, how would our new $V$ know to separate the two substrings correctly? We cannot add a special character because our world is $\{0,1\}^*$. 2) If we flip the answers of $V$ don't we simply get the same condition that I mentioned, just with a $1$, like this: $\exists z \in \{0,1\}^{p(|x|)} \forall y \in \{0,1\}^{p(|x|)} : V(x,y,z)=1$? – Cauthon Jun 17 '15 at 6:26
• Oh I now understood that we may know $p_A,p_B$, so the verifier knows where to separate the strings. However the complement closure is still unclear to me. – Cauthon Jun 17 '15 at 7:28
• right, we know $p_1,p_2$ so we can pad the $y,z$ to their full length (in case they are shorter). About the complement, note that I switched $y$ and $z$, that is, $V(x,z,y)$. I'll try to (think about it again, and) write a longer answer later (unless someone else will reply by then) – Ran G. Jun 17 '15 at 14:18
• That's clever! I haven't noticed that you changed the order of $z$ and $y$. I got it now. Thanks so much for both ideas! – Cauthon Jun 17 '15 at 14:47