Algoritmo de Atlantic City

El algoritmo de Atlantic City es un algoritmo polinomial probabilistico que contesta correctamente al menos el 75% de las veces (o, en algunas versiones diferentes, algún otro valor mayor que el 50%). El término "Atlantic City" fue introducido por primera vez en 1982 por J.Finn en un manuscrito que no se publicó titulado "Comparison of probabilistic tests for primality".^[1]

Relación con otros algoritmos probabilisticos[editar]

Otras dos clases comunes de algoritmos probabilisticos son el algoritmo de Monte Carlo y algoritmo de Las Vegas.Los algoritmos de Monte Carlo siempre son rápidos, pero solo "probablemente correctos"(no es asegurable en su totalidad que el resultado sea correcto). Por otra parte, el algoritmo de Las Vegas siempre son correctos, pero solo "probablemente rápido"(no son rápidos en todos los casos posibles que se puedan plantear). Los algoritmos de Atlantic City que se saltan algoritmos temporales polinomiales probabilisticos son probablemente correctos y probablemente rápidos (reúnen ambos algoritmos, el Algoritmo de Monte Carlo y Algoritmo de Las Vegas).^[2]

En el algoritmo de Atlantic City es, por definición, probablemente correcto y probablemente rápido. Esto indica que en un porcentaje bastante elevado, podemos estar seguros de que el resultado final será correcto y se obtendrá de manera bastante rápida. Como se indica anteriormente, el algoritmo de Atlantic City está basado en el algoritmo de Montecarlo y el algoritmo de Las Vegas. Ambos algoritmos tienen características similares al algoritmo tratado en esta publicación, pero ninguno de ellos reúne al completo las propiedades de este.

Origen del algoritmo de Atlantic City[editar]

El nombre de este algoritmo es ciertamente de procedencia desconocida, aunque muchos autores atribuyen su nombre a la ciudad de Atlantic City (Nueva Jersey), reconocida a nivel mundial por su abundancia de casinos, y la consecuente relación con los juegos de azar;al igual que los dos algoritmos con los que se relaciona, el nombre tiene origen en una ciudad relacionada con los casinos y juegos de azar.

J.Finn introdujo por primera vez el término de algoritmo de Atlantic City en 1982, en un manuscrito personal que nunca llegó a ser publicado y, que fue estudiado por otros autores y estudiosos con posterioridad.^{[cita requerida]}

Véase también[editar]

Referencias[editar]

↑ Mollin, Richard A. (2003). RSA and Public Key Cryptography. CHAPMAN & HALL/CRC. p. p. 80.
↑ William J Turner (mayo de 2002). «Black Box Linear Algebra with the Linbox Library (PDF). . p. 3. Retrieved .» (en inglés). North carolina State University. Consultado el 7 de marzo de 2017.

Datos: Q17513892

[1] Mollin, Richard A. (2003). RSA and Public Key Cryptography. CHAPMAN & HALL/CRC. p. p. 80.

[2] William J Turner (mayo de 2002). «Black Box Linear Algebra with the Linbox Library (PDF). . p. 3. Retrieved .» (en inglés). North carolina State University. Consultado el 7 de marzo de 2017.

[1]

[2]