6
$\begingroup$

I was looking at the following wikipedia article on the RP complexity class:

https://en.wikipedia.org/wiki/RP_(complexity)

In its definition it states:

  • If the correct answer is NO then it always returns NO
  • If the correct answer is YES then it returns YES with a probability of 1/2

At the end of the introduction it says:

The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm.

What I don't understand is why this 1/2 is arbitrary? If you change it to 1/3 does it really still contain the same set of decision problems as with 1/2?

$\endgroup$
8
$\begingroup$

Yes, the constant is entirely arbitrary. Call an algorithm a $p$-algorithm if:

  • When the correct answer is NO, it always answers NO.

  • When the correct answer is YES, it answers YES with probability at least $p$.

Note that the probability in the YES case is only over the algorithm's coin tosses.

Given a $p$-algorithm and a constant parameter $m$, we construct a new algorithm which runs the original algorithm $m$ times (with independent coin tosses) and takes the OR of the result. This algorithm is a $1-(1-p)^m$-algorithm (exercise). For every constant $q < 1$ you can find a constant $m$ such that $1-(1-p)^m \geq q$. Hence if a problem admits a $p$-algorithm it also admits a $q$-algorithm, for every $0 < p,q < 1$.

$\endgroup$
  • 1
    $\begingroup$ Great answer. It touches the fundamental characteristic of RP, the fact the the problem is solved probabilistically. The correct answer can be "guessed" with high confidence by iterating the solution. $\endgroup$ – ZeroUltimax Sep 23 '15 at 13:22

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.