# 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:

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

• You don't need to know the division of the word $x$. You can be provided with the division as part of the witness. – Yuval Filmus Mar 22 at 22:57
• Yeah, that's what I thought. So say that the witness provides me with the division, then I can simply divide it and check through the witnesses of $S_1, S_2$ if the words-parts are in $S_1, S_2$. But how would I define the witness "formally"? – Iam Spano Mar 22 at 22:59
• You’ve just defined it formally. – Yuval Filmus Mar 22 at 23:18

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