Types of randomized algorithms

A Las Vegas algorithm is an algorithm that runs in polynomial time and produces an answer with probability $\ge 1/2$; alternatively, it may say ``don't know.'' Whenever an answer is produced, it is guaranteed to be correct. By repeating the algorithm $k$ times using independent coin flips, the probability of not getting an answer is reduced to $1/2^k$.

A Monte Carlo algorithm with one-sided error runs in polynomial time and it produces a correct answer with probability $\geq 1/2$. The primality tests discussed in the previous class are examples of Monte Carlo algorithms with one-sided error, i.e., the answer ``$X$ is composite'' is always correct but ``$X$ is prime'' may be an incorrect answer; the probability that a composite $X$ is misclassified as prime is less than $1/2^k$ (after $k$ repetitions).