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


9

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{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:MODm

MODm(x1,,xk)={1 if xi0modm 0 if xi0modm 

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 MOD6 (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 MODm 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 ORMODm .

Szukam dowodu na to roszczenie lub przynajmniej jakiś kierunek.


1
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

1
Myślę, że , liczba zmiennych wejściowych, różni się od , moduł? nn
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

Odpowiedzi:


9

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.ORMOD


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?
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.