Изменения
Нет описания правки
# Докажите, что не существует схем константной глубины для функций $x_1 \oplus ... \oplus x_n$.
# Докажите, что не существует схемы константной глубины для сложения.
# Постройте схему из функциональных элементов с тремя входами: $x, y, z$ и одним выходом. Значение на выходе равно $x$, если $z=0$ и $y$, если $xz=1$. Используйте базис из всех не более чем бинарных функций.
# Мультиплексор - функциональная схема с $n = 2^k + k$ и одним выходом. Обозначим первые $2^k$ входов как $x_0, x_1, \ldots, x_{2^k-1}$, а оставшиеся $k$ как $y_0, y_1, \ldots, y_{k-1}$. Выход мультиплексора равен $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$. Постройте схему линейного от $n$ размера для мультиплексора.
# Дешифратор - функциональная схема с $k + 1$ входом и $n = 2^k$ выходами. Обозначим первые $k$ входов как $y_0, y_1, \ldots, y_{k-1}$, а последний как $z$. Обозначим выходы дешифратора как $x_0, x_1, \ldots, x_{2^k-1}$. Значение на выходах дешифратора 0 на всех выходах, кроме $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$, а на выходе $x_i$ равно значению $z$. Постройте схему линейного размера для дешифратора.
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
</wikitex>
