Семинары: В. И. Яшин, Лекция 2. Модель вычислений на булевых схемах, вероятностные вычисления

СЕМИНАРЫ


Открытые лекции по теме «Квантовые вычисления» 19 февраля 2025 г. 14:45, г. Москва, МИАН, комн. 430 (ул. Губкина, 8)

Лекция 2. Модель вычислений на булевых схемах, вероятностные вычисления В. И. Яшин
https://youtu.be/maW5_YtCJAs Аннотация: Мы обсудили несколько примеров решения задач при помощи булевых схем и определили класс сложности $\mathtt{P}$ в терминах булевых схем. Затем мы обсудили случайные биты и вероятностные булевы схемы, определили класс языков $\mathtt{BPP}$, эффективно разрешимых при помощи вероятностных булевых схем, и доказали теорему о снижении ошибки в вероятностных вычислениях.