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

Резюме доклада:
Вероятностные алгоритмы являются простейшими и самыми быстрыми известными решениями для многих задач разрешимости. Мы рассуждаем о вероятностных алгоритмах при помощи вероятностных машин Тьюринга, вариантом недетерминированных машин Тьюринга, которые принимают решения о переходах на основании вероятностей.

Цель этого доклада — обсуждение различных классов сложности, связанных с вероятностными вычислениями (BPP, RP, ZPP). Мы начнём с обзора этих классов, а также известных отношений между ними и классами, изучаемыми в курсе 1-БИ (P, NP).

Дальше мы посмотрим на то, как вероятностные алгоритмы дают намного более эффективные решения, чем дают детерминированные. Мы рассмотрим лемму Шварца-Зиппеля и её приложение к проверке равенства многочленов, что позволяет получить алгоритм Монте-Карло с полиномиальным временем исполнения в отличии от всех детерминированных аналогов, которые экспоненциальные.

В завершение мы обсудим открытый вопрос "P = BPP" и использование генераторов псевдослучайных чисел для детерминированной симуляции вероятностных алгоритмов.

Оригинал (CC-BY Churchill College): https://www.youtube.com/watch?v=Gvp-i_gEOao
Картинка для превью (CC-BY PierreSelim): https://en.wikipedia.org/wiki/File:Dice_-_1-2-4-5-6.jpg

Видео Дарья Дику о вероятностных вычислениях канала edyo.ru