Prove that $S_2$ is closed under union and complement

Question

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

Answer 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).