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

Мы обсудили несколько примеров решения задач при помощи булевых схем и определили класс сложности $\mathtt{P}$ в терминах булевых схем. Затем мы обсудили случайные биты и вероятностные булевы схемы, определили класс языков $\mathtt{BPP}$, эффективно разрешимых при помощи вероятностных булевых схем, и доказали теорему о снижении ошибки в вероятностных вычислениях.