Дарья Дику о вероятностных вычислениях

Резюме доклада: Вероятностные алгоритмы являются простейшими и самыми быстрыми известными решениями для многих задач разрешимости. Мы рассуждаем о вероятностных алгоритмах при помощи вероятностных машин Тьюринга, вариантом недетерминированных машин Тьюринга, которые принимают решения о переходах на основании вероятностей. Цель этого доклада — обсуждение различных классов сложности, связанных с вероятностными вычислениями (BPP, RP, ZPP). Мы начнём с обзора этих классов, а также известных отношений между ними и классами, изучаемыми в курсе 1-БИ (P, NP). Дальше мы посмотрим на то, как вероятностные алгоритмы дают намного более эффективные решения, чем дают детерминированные. Мы рассмотрим лемму Шварца-Зиппеля и её приложение к проверке равенства многочленов, что позволяет получить алгоритм Монте-Карло с полиномиальным временем исполнения в отличии от всех детерминированных аналогов, которые экспоненциальные. В завершение мы обсудим открытый вопрос “P = BPP“ и использование генер