Алгоритм Атлантик-Сити - Atlantic City algorithm

An Алгоритм Атлантик-Сити это вероятностный полиномиальное время алгоритм который отвечает правильно по крайней мере в 75% случаев (или, в некоторых версиях, какое-то другое значение больше 50%). Термин «Атлантик-Сити» впервые был введен в 1982 г. Дж. Финн в неопубликованной рукописи под названием Сравнение вероятностных тестов на простоту.[1]

Два других общих класса вероятностных алгоритмов: Алгоритмы Монте-Карло и Алгоритмы Лас-Вегаса. Алгоритмы Монте-Карло всегда быстрые, но только, вероятно, правильные. С другой стороны, алгоритмы Лас-Вегаса всегда верны, но только, вероятно, быстро. Алгоритмы Атлантик-Сити, которые представляют собой алгоритмы с ограниченным вероятностным полиномиальным временем, вероятно, верны и, вероятно, быстры.[2]

Рекомендации

  1. ^ Ричард А. Моллин (2003). RSA и криптография с открытым ключом. ЧАПМАН И ЗАЛ / CRC. п. 80.
  2. ^ Уильям Дж. Тернер (май 2002 г.). Линейная алгебра черного ящика с библиотекой Linbox. Государственный университет Северной Каролины. п. 3. Получено 10 июля 2014.