Abstract

• There are also a number of discrete problems for which only an exact result is acceptable (eg. sorting and searching) and where the introduction of randomness influences only on the ease and efficiency in finding the solution. For some problems where trivial exhaustive search is not feasible probabilistic algorithms can be applied giving a result that is correct with a probability less than one (eg. primality testing, string equality testing). The probability of failure can be made arbitrary small by repeated applications of the algorithm.