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

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

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

См. также [ править ]

Ссылки [ править ]

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

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .

[1] Ричард А. Моллин (2003). RSA и криптография с открытым ключом . ЧЭПМАН И ХОЛЛ/CRC. п. 80.

[2] Уильям Дж. Тернер (май 2002 г.). Линейная алгебра черного ящика с библиотекой Linbox . Государственный университет Северной Каролины. п. 3 . Проверено 10 июля 2014 г.

[1]

[2]