The purpose of this exercise is to compare Monte Carlo algorithms
and Las Vegas algorithms. In a nutshell, Monte Carlo algorithms
guarantee the running time but cannot guarantee correctness;
Las Vegas algorithms, on the other hand, guarantee correctness
but cannot guarantee the running time. Suppose we consider some
computational problem P for which we are given both a Monte Carlo
algorithm and a Las Vegas algorithm. For simplicity, assume
P is a decision problem, so that the answer
is either yes or no. Assume also that the
error probability of the given Monte Carlo algorithm is 1/4.
(a) Show how to design a Monte Carlo algorithm for P
of arbitrarily small error probability. (Hint:
First design another Monte Carlo algorithm for P
from the given one whose error probability is,
for definiteness, less than 1/6. Generalize the construction.)
(b) Which type of algorithm, Monte Carlo or Las Vegas,
is more powerful? In other words, it is possible to convert
one type to the other? (Hint: Yes.)