Obwody o głębokości 2 z bramkami OR i MOD nie są uniwersalne?

Dobrze wiadomo, że każdą funkcję boolowską można zrealizować za pomocą obwodu boolowskiego o głębokości 2 (ponad zmiennymi, ich negacją i stałymi wartościami) zawierający bramki AND na pierwszym poziomie i jedną pojedynczą bramkę OR na górnym poziomie; jest to po prostu przedstawienie DNF z . $f:\{0,1\}^n\to \{0,1\}$ $f$

Innym rodzajem bramki, która jest bardzo interesująca ze względu na złożoność obwodów, jest bramka . Zwykła definicja jest następująca: $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$ \\ }$

Bramy te mają czasem zaskakującą moc; na przykład, dowolna funkcja boolowska może być reprezentowana przez obwód głębokości-2 mający tylko bramy $\mathrm{MOD}_6$ (jest to folklor, ale mogę rozwinąć, czy ktoś jest zainteresowany).

Jednak innym folklorem jest to, że obwody z pojedynczą bramą OR na górze i bramkami $\mathrm{MOD}_m$ w dolnej warstwie (przy czym $m$ jest ustalone raz na zawsze, a w szczególności są takie same dla wszystkich bram) nie jest uniwersalny, tj. dla dowolnej wartości $m$ , istnieją funkcje boolowskie, których nie można obliczyć w obwodzie $\mathrm{OR} \circ \mathrm{MOD}_m$ .

Szukam dowodu na to roszczenie lub przynajmniej jakiś kierunek.

complexity-theory logic circuits

— Gadi A.
źródło

W pierwszym akapicie albo nie potrzebujesz bramek, albo musisz powiedzieć „każda monotoniczna funkcja boolowska”.

— Tsuyoshi Ito

Masz rację; typowe założenie jest takie, że masz jako dane wejściowe zmienne, ich negację, a także dowolne wartości (ważne dla modgates). Napiszę to wprost.

— Gadi

Myślę, że , liczba zmiennych wejściowych, różni się od , moduł?

n

$n$

n

$n$

— Kristoffer Arnsfelt Hansen

Tak, przepraszam za to.

— Gadi

Jestem tym zainteresowany. Czy znasz jakieś odniesienia do pierwszego faktu folklorystycznego? Zastanawiam się, czy jeśli w drugiej klasie obwodów dopuszczasz tylko jedno OR, ile dopuszczasz w pierwszym?

— Juan Bermejo Vega

Nie można obliczyć funkcji logicznej AND. Załóżmy, że funkcja AND jest obliczana przez obwód . Wynika z tego, że jeden z obwodów MOD musi już wtedy obliczyć funkcję ORAZ, co jest niemożliwe. $\text{OR} \circ \text{MOD}$

— Kristoffer Arnsfelt Hansen
źródło

Nie, on ma rację. Domyślne założenie jest takie, że n jest stałe i powinniśmy być w stanie obsłużyć dowolnie dużą liczbę danych wejściowych za pomocą bramek mod_n.

— Gadi

@GadiA Ah, ok. Nie było to jasne w twoim pytaniu, przynajmniej dla ludzi, którzy nie znają tej dziedziny. Dokonałem drobnej zmiany, która powinna to wyjaśnić.

— Gilles „SO- przestań być zły”

Tak, moje pytanie było bardzo źle sformułowane, przepraszam.

— Gadi

@Gilles Czy możesz mi wyjaśnić, którego fan-u tutaj rozważamy? Problemem jest dla mnie to, że nie rozumiem, dlaczego pod-obwód MOD nie może obliczyć AND? Ile wejść ma ten MOD i ten AND?