Un algoritmo de Atlantic City es un algoritmo de tiempo polinomial probabilístico que responde correctamente al menos el 75% del tiempo (o, en algunas versiones, algún otro valor superior al 50%). El término "Atlantic City" fue introducido por primera vez en 1982 por J. Finn en un manuscrito inédito titulado Comparación de pruebas probabilísticas de primalidad . [1]
Otras dos clases comunes de algoritmos probabilísticos son los algoritmos de Monte Carlo y los algoritmos de Las Vegas . Los algoritmos de Monte Carlo son siempre rápidos, pero probablemente correctos. Por otro lado, los algoritmos de Las Vegas siempre son correctos, pero probablemente rápidos. Los algoritmos de Atlantic City, que son algoritmos de tiempo polinomial probabilístico acotado, probablemente sean correctos y probablemente rápidos. [2]
Referencias
- ^ Richard A. Mollin (2003). RSA y criptografía de clave pública . CHAPMAN & HALL / CRC. pag. 80.
- ^ William J. Turner (mayo de 2002). Álgebra lineal de caja negra con la biblioteca Linbox . Universidad Estatal de Carolina del Norte. pag. 3 . Consultado el 10 de julio de 2014 .