I'm trying to prove the following problem:

Show that $RP$ is closed under concatenation

Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the TM of $L_{1}$ accepted the first part of the word (with a probability $\geq\frac{1}{2}$), and the TM of $L_{2}$ accepted the second part of the word (with a probability $\geq\frac{1}{2}$).

But then each word in the language $L_{1} \circ L_{2}$ would be accept with a probability of $\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$, so the language $L_{1} \circ L_{2}$ will not be in $RP$.

So what is the correct proof to the problem?

  • 1
    $\begingroup$ Hint: amplify the success probability. $\endgroup$ – Yuval Filmus Sep 1 '18 at 22:16

Do the following $poly(|x|)$ times:

Check for every possible (contiguous) partition of the input string $x = x_1x_2$ and apply the $\mathrm{RP}$ machine to each of $x_i$ if the answer is $\mathrm{YES}\:\mathrm{YES}$ outputs $\mathrm{YES}$ and halt.

If after polynomially many times, still no definite $\mathrm{YES}$ answer has been put down, output $\mathrm{NO}$ with a little bit of fear as it is always like so with $\mathrm{RP}$ algorithms.

  • $\begingroup$ In fact, it suffices to repeat a constant number of times. $\endgroup$ – Yuval Filmus Sep 2 '18 at 7:18

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.