| You can help expand this article with text translated fromthe corresponding article in French. (June 2022)Click [show] for important translation instructions.- View a machine-translated version of the French article.
- Machine translation, likeDeepL orGoogle Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia.
- Consideradding a topic to this template: there are already 1,159 articles in themain category, and specifying
|topic= will aid in categorization. - Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article.
- Youmust providecopyright attribution in theedit summary accompanying your translation by providing aninterlanguage link to the source of your translation. A model attribution edit summary is
Content in this edit is translated from the existing French Wikipedia article at [[:fr:Algorithme d'Atlantic City]]; see its history for attribution. - You may also add the template
{{Translated|fr|Algorithme d'Atlantic City}} to thetalk page. - For more guidance, seeWikipedia:Translation.
|
Computer science algorithm
Atlantic City algorithm is aprobabilisticpolynomial timealgorithm (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 byJ. Finn in an unpublished manuscript entitledComparison of probabilistic tests for primality.[1]
Two other common classes of probabilistic algorithms areMonte Carlo algorithms andLas 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][3]
