Схемы глубины-2 с элементами OR и MOD не являются универсальными?

Question

Хорошо известно, что каждая булева функция $ f:\{0,1\}^n o \{0,1\}$ может быть реализована с использованием булевой схемы глубиной 2 (по переменным, их отрицанию и постоянным значениям), содержащей элементы И на первом уровне и один единственный элемент ИЛИ на верхнем уровне;это просто Представление DNF из $f$.

Другим типом вентилей, представляющим большой интерес с точки зрения сложности схемы, является вентиль $MOD_m$.Обычное определение заключается в следующем:

$$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{ 1 & if \(\sum x_i \equiv 0 \mod m\) \\ 0 & if \(\sum x_i ot\equiv 0 \mod m \) \\ }$$

Эти врата иногда обладают удивительной силой;например, любая логическая функция может быть представлена схемой глубины 2, имеющей только вентили $ \ mathrm {MOD} _6 $ (это фольклор, но я могу уточнить, если кому-то интересно).

Однако другой фольклор заключается в том, что схемы с одним элементом OR наверху и элементами $ \ mathrm {MOD} _m $ в нижнем слое (при этом $ m $ фиксируется раз и навсегда и, в частности, является одинаковым для всех элементов) не являются универсальными, т.е.для любого значения $m $ существуют логические функции, которые не могут быть вычислены с помощью $\mathrm{ИЛИ} \circ \mathrm{MOD}_m$ circuit.

Я ищу доказательства этого утверждения или, по крайней мере, какое-то направление.

Answer 1

Логическое значение И функция не могут быть вычислены.Предположим на самом деле, что функция AND вычисляется с помощью схемы $ ext{OR} \circ ext{MOD}$.Тогда из этого следует, что одна из подсхем MOD должна тогда вычисляться И уже функционировать, что невозможно.