Atlantic City algorithm

{{expand French|Algorithme d'Atlantic City|category=Articles needing translation from French Wikipedia|date=June 2022}}

{{Short description|Computer science algorithm}}

Atlantic City algorithm is a probabilistic polynomial time algorithm (PP Complexity Class) that answers correctly at least 75% of the time (or, in some versions, some other value greater than 50%). The term "Atlantic City" was first introduced in 1982 by J. Finn in an unpublished manuscript entitled Comparison of probabilistic tests for primality.{{cite book|last1=Richard A. Mollin|title=RSA and Public Key Cryptography|date=2003|publisher=CHAPMAN & HALL/CRC|page=80}}

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.{{cite book|last1=William J. Turner|title=Black Box Linear Algebra with the Linbox Library|date=May 2002|publisher=North carolina State University|page=3|url=https://repository.lib.ncsu.edu/handle/1840.16/3025|accessdate=10 July 2014}}