Лекция 2. Схемная модель вычислений

На Лекции мы продолжили обсуждение различных свойств классических булевых схем. Любая булева операция содержит некоторое число бит на входе и на выходе. Зачастую естественно считать, что все вентили из словаря имеют конечный вход, поскольку физически реализуемые операции над битами как правило локальны. С другой стороны, поскольку классическую информацию дёшево копировать, зачастую удобно считать, что на число линий на выходе вентиля не ограниченно по $n$. Если принять такое соглашение, и если словарь универсален, то любую функцию можно реализовать за линейную глубину. Также, мы показали при помощи подсчёта, что большинство булевых функций требует экспоненциального числа операций. На протяжении курса нас часто будет интересовать не-универсальный класс афинных булевых функций. Такие функции связаны с линейной алгеброй над $\mathbb{Z}_2$ и их просто реализовывать схемами из словаря $\{\mathrm{NOT},\mathrm{XOR}\}$. Над пространством булевых функций можно ввести преобразование Уолша-Адамара-Фурье. Фурье-преобразованиями линейных булевых функций являются в точности $\delta$-функциями. При помощи семейств булевых схем возможно разрешать языки, и сложность языка определяется сложностью построения таких семейств.