Цепи глубины-2 с вентилями OR и MOD не универсальны?

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

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

{M O D}_{m} (x_{1}, \dots, x_{k}) = {\begin{cases} 1 & if \sum x_{i} \equiv 0 \mod m \\ 0 & if \sum x_{i} ≢ 0 \mod m \end{cases}

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

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

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

Я ищу подтверждение этому требованию или хотя бы какое-то направление.

complexity-theory logic circuits Гади А
источник

В первом абзаце вам либо НЕ нужны вентили, либо вы должны сказать «каждая монотонная булева функция».

Цуёси Ито

Ты прав; Обычно предполагается, что в качестве входных данных у вас есть переменные, их отрицание, а также произвольные значения (важно для modgates). Я напишу это явно.

Гади А

Я думаю, что , количество входных переменных, отличается от , модуль?

n

$n$

n

$n$

Кристоффер Арнсфельт Хансен

Да, извините за это.

Гади А

Я заинтересован в этом. Знаете ли вы ссылку на первый фольклорный факт? Интересно, если в последнем классе цепей вы разрешаете только одно ИЛИ, сколько вы разрешаете в первом?

Хуан Бермехо Вега

Булева функция AND не может быть вычислена. Предположим, что функция AND вычисляется схемой . Затем следует, что одна из подсхем MOD уже должна вычислять функцию AND, что невозможно. $\text{OR} \circ \text{MOD}$

Кристоффер Арнсфельт Хансен
источник

Нет, он прав. Здесь подразумевается, что n является константой, и мы должны иметь возможность обрабатывать произвольно большое количество входов с помощью логических элементов mod_n.

Гади А

@GadiA Ах, хорошо. Это не было ясно в вашем вопросе, по крайней мере, для людей, которые не знакомы с этой областью. Я сделал небольшое изменение, которое должно прояснить это.

Жиль "ТАК - перестать быть злым"

Да, мой вопрос был очень плохо сформулирован, извините.

Гади А

@ Жиль Можете ли вы объяснить мне, что фан-здесь мы рассматриваем? Проблема для меня в том, что я не могу понять, почему подсистема MOD не может вычислить AND? Сколько входов имеет этот мод и это И?

Цепи глубины-2 с вентилями OR и MOD не универсальны?

Ответы: