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