Prove/Disprove: NP is closed under "mixed" complexity

Question

Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that:

1. $\displaystyle x_{i} \in \{0,1\}^{*}$

2. $\displaystyle x_{1} x_{3} ...x_{n-1} \in S_{1}$

3. $\displaystyle x_{2} x_{4} ...x_{n} \in S_{2}$

Prove or disprove: if $\displaystyle S_{1} ,S_{2} \in NP$, then $\displaystyle S_{1}°S_{2} \in NP$

I have a feeling it is a proof, simply because I wouldn't know how to disprove it. I know it should come down to finding a certificate $\displaystyle c$ such that $\displaystyle V( x,c) =1$ if'f $\displaystyle x\in S_{1}°S_{2}$, based on the certificates of $\displaystyle S_{1} ,S_{2}$.

The thing is I don't really know what the division of the word $\displaystyle x$ is. So how can I check if part of the word is in $\displaystyle S_{1}$ and the other in $\displaystyle S_{2}$? I could maybe define the $\displaystyle c$ in this way, that it gives you the division, but I don't really know how to define it properly.

Any help?

Keep in mind that's the first time for me studying this subject

Answer 1

The language $S = S_1 \circ S_2$ (I'm assuming that was the intended notation) is in NP if $S_1,S_2$ are in NP. Indeed, given verifiers for $S_1,S_2$, we can construct a non-deterministic verifier for $S$ as follows:

Given an input $x \in \{0,1\}^*$, guess a decomposition $x = x_1 \ldots x_n$ for even $n$, and use the verifiers for $S_1,S_2$ to verify that $x_1x_3 \ldots x_{n-1} \in S_1$ and $x_2x_4 \ldots x_n \in S_2$.

In terms of witnesses, a witness for $x \in S$ has the following form:

1. An even number $n$ and $n$ strings $x_1,\ldots,x_n$.
2. A witness $w_1$ for $S_1$.
3. A witness $w_2$ for $S_2$.

To verify this witness, we check:

1. $x = x_1 \ldots x_n$.
2. $w_1$ is a witness for $x_1 x_3 \ldots x_{n-1} \in S_1$.
3. $w_2$ is a witness for $x_2 x_4 \ldots x_n \in S_2$.