# 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