kleinste Schaltungsgröße unter Verwendung von XOR-Gattern

Angenommen, wir erhalten eine Menge von n booleschen Variablen x_1, ..., x_n und eine Menge von m Funktionen y_1 ... y_m, wobei jedes y_i das XOR einer (gegebenen) Teilmenge dieser Variablen ist. Das Ziel besteht darin, die minimale Anzahl von XOR-Operationen zu berechnen, die Sie ausführen müssen, um alle diese y_1 ... y_m-Funktionen zu berechnen.

Beachten Sie, dass das Ergebnis einer XOR-Operation, z. B. x_1 XOR x_2, bei der Berechnung mehrerer y_j verwendet werden kann, aber als eins gezählt wird. Beachten Sie auch, dass es nützlich sein kann, XOR einer viel größeren Sammlung von x_i zu berechnen (größer als jede y_i-Funktion, z. B. XOR aller x_i), um y_i effizienter zu berechnen.

Angenommen, wir haben eine binäre Matrix A und einen Vektor X, und das Ziel ist, den Vektor Y so zu berechnen, dass AX = Y ist, wobei alle in GF (2) ausgeführten Operationen eine minimale Anzahl von Operationen verwenden.

Auch wenn jede Zeile von A genau k hat (sagen wir k = 3), ist das interessant. Kennt jemand die Komplexität (Härte der Approximation) dieser Frage?

Mohammad Salavatiopur

Das ist NP-schwer. Siehe: Joan Boyar, Philip Matthews, René Peralta. Techniken zur Logikminimierung mit Anwendungen für die Kryptologie. http://link.springer.com/article/10.1007/s00145-012-9124-7

Die Reduktion ist von Vertex Cover und ist sehr schön.

Gegeben sei ein Graph mit m = | E | Definieren Sie eine m × ( n + 1 ) -Matrix A als: A [ i , j ] = 1, wenn j < n + 1 und ( i , j ) ≤ E , und A [ i , $(\{1,\ldots,n\},E)$$m=|E|$$m \times (n+1)$$A$$A[i,j] = 1$$j < n+1$$(i,j) \in E$ . Mit anderen Worten, mit n + 1 Variablen x 1 , … , x n + 1 wollen wir die m linearen Formen x i + x j + x n + 1 für alle ( i , j ) ∈ E berechnen$A[i,n+1] = 1$$n+1$$x_1,\ldots,x_{n+1}$$m$$x_i+x_j+x_{n+1}$$(i,j) \in E$ .

Ein kleiner Gedanke zeigt, dass es eine XOR-Schaltung für mit Gates of Fan-In Two gibt, die die lineare Transformation A mit nur m + k Gates berechnet , wobei k die optimale Scheitelpunktabdeckung für den Graphen ist. (Berechnen Sie zuerst x i ' + x n + 1 für alle i ' in der Vertexbedeckung unter Verwendung von k Operationen. Die linearen Formen sind dann alle in m berechenbar$A$$A$$m+k$$k$$x_{i'} + x_{n+1}$$i'$$k$$m$ weiteren Operationen .) Es stellt sich heraus, dass dies auch eine Schaltung mit minimaler Größe ist!

Der Beweis, dass die Reduzierung korrekt ist, ist nicht so schön. Ich würde gerne einen kurzen Beweis dafür sehen, dass diese Reduzierung korrekt ist.