Editing Monte Carlo algorithm (section)

==One-sided vs two-sided error==
While the answer returned by a [[deterministic algorithm]] is always expected to be correct, this is not the case for Monte Carlo algorithms. For [[decision problem]]s, these algorithms are generally classified as either '''false'''-biased or '''true'''-biased. A '''false'''-biased Monte Carlo algorithm is always correct when it returns '''false'''; a '''true'''-biased algorithm is always correct when it returns '''true'''. While this describes algorithms with ''one-sided errors'', others might have no bias; these are said to have ''two-sided errors''. The answer they provide (either '''true''' or '''false''') will be incorrect, or correct, with some bounded probability.

For instance, the [[Solovay–Strassen primality test]] is used to determine whether a given number is a [[prime number]]. It always answers '''true''' for prime number inputs; for composite inputs, it answers '''false''' with probability at least {{frac|1|2}} and '''true''' with probability less than {{frac|1|2}}. Thus, '''false''' answers from the algorithm are certain to be correct, whereas the '''true''' answers remain uncertain; this is said to be a ''{{frac|1|2}}-correct false-biased algorithm''.