Atlantic City algorithm
An Atlantic City algorithm is a a probabilistic polynomial-time algorithm that answers correctly at least seventy-five percent of the time. In some versions of the algorithm, some value greater than 1/2 has been used instead of 3/4. The term "Atlantic City" was first introduced in 1982 by J. Finn in an unpublished manuscript entitled Comparison of probabilistic tests for primality.[1] Two other common classes of probabilistic algorithms are Monte Carlo algorithms and Las Vegas algorithms. Monte Carlo algorithms are always fast, but only probably correct. On the other hand, Las Vegas algorithms are always correct, but only probably fast. The Atlantic City algorithms which are bounded probabilistic polynomial time algorithms are probably correct and probably fast.[2]
References
- ^ Richard A. Mollin (2003). RSA and Public Key Cryptography. CHAPMAN & HALL/CRC. p. 80.
- ^ William J Turner (May 2002). Black Box Linear Algebra with the Linbox Library (PDF). North carolina State University. p. 3. Retrieved 10 July 2014.