Algoritmus Atlantic City - Atlantic City algorithm - Wikipedia

An Algoritmus Atlantic City je pravděpodobnostní polynomiální čas algoritmus který odpovídá správně alespoň 75% času (nebo v některých verzích jiná hodnota větší než 50%). Termín "Atlantic City" byl poprvé zaveden v roce 1982 J. Finn v nepublikovaném rukopisu s názvem Srovnání pravděpodobnostních testů na prvost.^[1]

Dvě další běžné třídy pravděpodobnostních algoritmů jsou Algoritmy Monte Carlo a Las Vegas algoritmy. Algoritmy Monte Carlo jsou vždy rychlé, ale jen pravděpodobně správné. Na druhou stranu jsou lasvegaské algoritmy vždy správné, ale jen pravděpodobně rychlé. Algoritmy v Atlantic City, které jsou ohraničené pravděpodobnostními polynomiálními časovými algoritmy, jsou pravděpodobně správné a pravděpodobně rychlé.^[2]

Reference

^ Richard A. Mollin (2003). Kryptografie RSA a veřejného klíče. CHAPMAN & HALL / CRC. str. 80.
^ William J. Turner (květen 2002). Black Box Linear Algebra with the Linbox Library. Státní univerzita v Severní Karolíně. str. 3. Citováno 10. července 2014.

P ≟ NP

Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Richard A. Mollin (2003). Kryptografie RSA a veřejného klíče. CHAPMAN & HALL / CRC. str. 80.

[2] William J. Turner (květen 2002). Black Box Linear Algebra with the Linbox Library. Státní univerzita v Severní Karolíně. str. 3. Citováno 10. července 2014.

[1]

[2]