I was looking at the following wikipedia article on the RP complexity class:
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?