Prove/Disprove: NP is closed under "mixed" complexity 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:

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

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

$\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
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:

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

To verify this witness, we check:

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