Tiefen-2-Schaltungen mit ODER- und MOD-Gattern sind nicht universell?

9

Es ist bekannt, dass jede Boolesche Funktion unter Verwendung einer Booleschen Schaltung der Tiefe 2 (über die Variablen, ihre Negation und konstanten Werte) realisiert werden kann. Enthält UND-Gatter in der ersten Ebene und ein einzelnes ODER-Gatter in der oberen Ebene; Dies ist einfach die DNF-Darstellung von .ff:{0,1}n→{0,1}f

Ein anderer der für die Schaltungskomplexität von großem Interesse ist, ist das Gatter. Die übliche Definition lautet wie folgt:MODm

MODm(x1,…,xk)={1 if ∑xi≡0modm 0 if ∑xi≢0modm 

Diese Tore haben manchmal überraschende Kraft; Zum Beispiel kann jede boolesche Funktion durch eine Tiefen-2-Schaltung mit nur MOD6 Gattern dargestellt werden (dies ist Folklore, aber ich kann näher darauf eingehen, wenn jemand interessiert ist).

Eine andere Folklore ist jedoch, dass Schaltungen mit einem einzelnen ODER-Gatter an der oberen und MODm Gattern in der unteren Schicht (wobei m ein für alle Mal festgelegt ist und insbesondere für alle Gatter gleich ist) nicht universal, dh für jeden Wert von m gibt es boolesche Funktionen, die nicht von \ mathrm {OR} \ circ \ mathrm {MOD} _m berechnet OR∘MODmwerden können.

Ich suche einen Beweis für diese Behauptung oder zumindest eine Richtung.

complexity-theory logic circuits Gadi A.
quelle
1
Im ersten Absatz benötigen Sie entweder KEINE Gatter oder Sie müssen "jede monotone Boolesche Funktion" sagen .
Tsuyoshi Ito
Du hast Recht; Die übliche Annahme ist, dass Sie als Eingaben die Variablen, ihre Negation und auch beliebige Werte (wichtig für Modgates) haben. Ich werde dies explizit schreiben.
Gadi A
1
Ich denke, dass , die Anzahl der Eingangsvariablen, sich von , dem Modul, unterscheidet. nn
Kristoffer Arnsfelt Hansen
Ja, tut mir leid.
Gadi A
Das interessiert mich. Kennen Sie einen Hinweis auf die erste folkloristische Tatsache? Ich frage mich, ob Sie in der letzteren Klasse von Schaltkreisen nur einen OP zulassen, wie viele erlauben Sie in der ersteren?
Juan Bermejo Vega

Antworten:

9

Die Boolesche AND-Funktion kann nicht berechnet werden. Angenommen, die UND-Funktion wird tatsächlich von einer -Schaltung berechnet . Daraus folgt, dass eine der MOD-Teilschaltungen dann bereits UND-Funktion berechnen muss, was unmöglich ist.OR∘MOD

Kristoffer Arnsfelt Hansen
quelle
Nein, er hat recht. Die implizite Annahme hier ist, dass n konstant ist und wir in der Lage sein sollten, eine beliebig große Anzahl von Eingaben mit mod_n-Gattern zu verarbeiten.
Gadi A
@GadiA Ah, ok. Dies war in Ihrer Frage nicht klar, zumindest für Leute, die mit dem Gebiet nicht vertraut sind. Ich habe eine kleinere Änderung vorgenommen, die dies verdeutlichen soll.
Gilles 'SO - hör auf böse zu sein'
Ja, meine Frage war sehr schlecht formuliert, sorry.
Gadi A
@ Gilles Kannst du mir erklären, welches Fan-In wir hier berücksichtigen? Das Problem für mich ist, dass ich nicht sehen kann, warum der Subcircuit von MOD AND nicht berechnen kann. Wie viele Eingänge hat dieser MOD und dieses UND?