Аннотация:
На этой Лекции мы обсудили, как формулировать решение вычислительных задач при помощи булевых схем. Язык $L$ лежит в классе сложности $\mathtt{P}$, если для него существует равномерное семейство булевых схем, такое, что машина Тьюринга, порождающая это семейство, работает за полиномиальное время. Мы рассмотрели пару примеров формулирования решения задач в терминах построения равномерных семейств булевых схем. Также, начали обсуждать вероятностные вычисления. Вероятностными булевыми схемами называются булевы схемы, в которых допускается приготовления равномерно случайных битов. Используя случайность, иногда удаётся более эффективно решать вычислительные задачи.
