Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Любое отображение $f: \mathbf{F}_{2}^{m} \rightarrow \mathbf{F}_{2}^{n}$ может быть представлено единственным вектором булевских многочленов.
Доказательство.
Достаточно рассмотреть случай $n=1$. Тогда $f$ представлено с помощью
\[
F\left(x_{1}, \ldots, x_{n}\right):=\sum_{y=\left(y_{i}\right) \in \mathbf{F}_{2}^{m}} f(y) \prod_{i}\left(x_{i}+y_{i}+1\right),
\]
так как произведение в (9) – дельта-функция в $x$ на $y$. Более того, пространства отображений и булевых полиномов имеют общую размерность $2^{m}$ над $\mathbf{F}_{2}$.
Теперь мы можем вычислить любой вектор булевых многочленов, повторяя операции из небольшого конечного списка, который выбирается и фиксируется, например, $\mathscr{B}:=\{x, 1, x+y, x y,(x, x)\}$. Такие операторы называются классическими гейтами. Последовательность таких операторов вместе с указанием их аргументов из ранее вычисленных битов называется булевской схемой. Число шагов вычисления в такой сети рассматривается как время (мера времени) вычисления.
Если соответствующие конечные множества – не $\mathbf{F}_{2}^{m}$ и, может, имеют неподходящее число элементов, будем кодировать их элементы конечными последовательностями битов и рассматривать сужение булевского многочлена на соответствующие подмножества.
Аналогично предыдущему, протокол вычисления в этой модели можно представить как конечную таблицу, состоящую из строк (в общем случае разной длины), которые представляют последовательности из нулей и единиц. Начальная строка этой таблицы – входные данные. Каждая следующая строка должна получаться из предыдущей строки путем применения одной из базовых функций в $\mathscr{B}$ к последовательности соседних битов (оставшиеся биты копируются без изменения). Последняя строка – выходные данные. Точное положение битов, которые изменяются в каждой строке, и способ изменения должны быть частью протокола.
Физически можно реализовать эти строки как различные регистры памяти или как последовательные состояния одного и того же регистра (тогда нам придется определить, как работать с переменной длиной, например, используя символы пробела).
