애틀랜틱 시티 알고리즘
Atlantic City algorithm아틀란틱 시티 알고리즘은 확률론적 다항식 시간 알고리즘으로, 적어도 75% 이상의 시간(또는 일부 버전에서는 50% 이상의 다른 값)을 정확하게 답한다."대서양 도시"라는 용어는 J. 핀에 의해 1982년 "최초성을 위한 확률론적 시험 비교"라는 제목의 미발표 원고에서 처음 소개되었다.[1]
확률론적 알고리즘의 다른 두 가지 일반적인 등급은 몬테카를로 알고리즘과 라스베가스 알고리즘이다.몬테카를로 알고리즘은 항상 빠르지만 아마도 정확할 것이다.반면에 라스베이거스 알고리즘은 항상 정확하지만, 아마도 빠를 것이다.확률론적 다항식 시간 알고리즘인 아틀란틱 시티 알고리즘은 정확하고 아마도 빠를 것이다.[2]
참고 항목
참조
- ^ Richard A. Mollin (2003). RSA and Public Key Cryptography. CHAPMAN & HALL/CRC. p. 80.
- ^ William J. Turner (May 2002). Black Box Linear Algebra with the Linbox Library. North carolina State University. p. 3. Retrieved 10 July 2014.
