1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ You don't need to know the division of the word $x$. You can be provided with the division as part of the witness. $\endgroup$ – Yuval Filmus Mar 22 at 22:57
  • $\begingroup$ 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"? $\endgroup$ – Iam Spano Mar 22 at 22:59
  • $\begingroup$ You’ve just defined it formally. $\endgroup$ – Yuval Filmus Mar 22 at 23:18
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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