2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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? $\endgroup$
    – Ran G.
    Jun 16, 2015 at 22:26
  • $\begingroup$ 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$? $\endgroup$
    – Cauthon
    Jun 17, 2015 at 6:26
  • $\begingroup$ 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. $\endgroup$
    – Cauthon
    Jun 17, 2015 at 7:28
  • 1
    $\begingroup$ 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) $\endgroup$
    – Ran G.
    Jun 17, 2015 at 14:18
  • $\begingroup$ 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! $\endgroup$
    – Cauthon
    Jun 17, 2015 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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