Randomized algorithm: Difference between revisions

Revision as of 15:53, 22 February 2021

Revision as of 19:38, 31 March 2021

Line 67:

==History==

Historically, the first randomized algorithm was a method developed by [[Michael O. Rabin]] for the [[closest pair of points problem|closest pair problem]] in [[computational geometry]].<ref>Smid, Michiel. Closest point problems in computational geometry. Max-Planck-Institut für Informatik|year=1995</ref>

The study of randomized algorithms was spurred by the 1977 discovery of a [[Solovay-StrassenSolovay–Strassen primality test|randomized primality test]] (i.e., determining the [[primality test|primality]] of a number) by [[Robert M. Solovay]] and [[Volker Strassen]]. Soon afterwards Michael O. Rabin demonstrated that the 1976 [[Miller-RabinMiller–Rabin primality test|Miller's primality test]] can be turned into a randomized algorithm. At that time, no practical [[deterministic algorithm]] for primality was known.

The Miller-RabinMiller–Rabin primality test relies on a binary relation between two positive integers ''k'' and ''n'' that can be expressed by saying that ''k'' "is a witness to the compositeness of" ''n''. It can be shown that

* If there is a witness to the compositeness of ''n'', then ''n'' is composite (i.e., ''n'' is not [[prime number|prime]]), and

* If ''n'' is composite then at least three-fourths of the natural numbers less than ''n'' are witnesses to its compositeness, and

Line 202:

* [[Michael Mitzenmacher|M. Mitzenmacher]] and [[Eli Upfal|E. Upfal]]. ''Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. Cambridge University Press, New York (NY), 2005.

* [[Rajeev Motwani]] and P. Raghavan. ''Randomized Algorithms''. Cambridge University Press, New York (NY), 1995.

* Rajeev Motwani and P. Raghavan. [http://portal.acm.org/citation.cfm?id=234313.234327 Randomized Algorithms.]. A survey on Randomized Algorithms.

* {{Citation|author = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 978-0-201-53082-7| author-link = Christos Papadimitriou }} Chapter 11: Randomized computation, pp.&nbsp;241–278.

* {{cite journal|doi=10.1016/0022-314X(80)90084-0|title=Probabilistic algorithm for testing primality|journal=Journal of Number Theory|volume=12|pages=128–138|year=1980|last1=Rabin|first1=Michael O.|doi-access=free}}