najmniejszy rozmiar obwodu za pomocą bramek XOR

Załóżmy, że otrzymujemy zestaw n zmiennych logicznych x_1, ..., x_n oraz zestaw funkcji m y_1 ... y_m, gdzie każdy y_i jest XOR (danego) podzbioru tych zmiennych. Celem jest obliczenie minimalnej liczby operacji XOR, które należy wykonać, aby obliczyć wszystkie te funkcje y_1 ... y_m.

Zauważ, że wynik operacji XOR, powiedzmy x_1 XOR x_2 może być użyty do obliczenia wielu y_j, ale jest liczony jako jeden. Zauważ też, że użyteczne może być obliczenie XOR znacznie większej kolekcji x_i (większej niż jakakolwiek funkcja y_i, np. Obliczenie XOR wszystkich x_i) w celu bardziej wydajnego obliczenia y_i,

Równolegle załóżmy, że mamy macierz binarną A i wektor X, a celem jest obliczenie wektora Y w taki sposób, że AX = Y, gdzie wszystkie operacje wykonane w GF (2) przy użyciu minimalnej liczby operacji.

Nawet jeśli każdy wiersz A ma dokładnie k jeden (powiedzmy k = 3), jest interesujący. Czy ktoś wie o złożoności (twardości przybliżenia) tego pytania?

Mohammad Salavatiopur

To trudne NP. Patrz: Joan Boyar, Philip Matthews, René Peralta. Techniki minimalizacji logiki z zastosowaniem aplikacji w kryptologii. http://link.springer.com/article/10.1007/s00145-012-9124-7

Redukcja pochodzi od Cover Vertex i jest bardzo ładna.

Biorąc pod uwagę wykres z m = | E | , zdefiniuj macierz m × ( n + 1 ) A jako: A [ i , j ] = 1, jeżeli j < n + 1 oraz ( i , j ) ∈ E , i A [ i , $(\{1,\ldots,n\},E)$$m=|E|$$m \times (n+1)$$A$$A[i,j] = 1$$j < n+1$$(i,j) \in E$ . Innymi słowy, zważywszy n + 1 zmiennych x 1 , ... , x n + 1 chcemy obliczyć m liniowej formy x I + x j + x n + 1 dla wszystkich ( i , j ) ∈ E .$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$

Mała myśl pokazuje, że istnieje obwód XOR dla z bramkami wachlarza dwóch obliczającymi transformację liniową A tylko z bramkami m + k , gdzie k jest optymalną osłoną wierzchołków dla wykresu. (Najpierw oblicz x i ′ + x n + 1 dla wszystkich i ′ w pokrywie wierzchołka, używając operacji k . Wszystkie formy liniowe są następnie obliczalne w m większej liczbie operacji.) Okazuje się, że jest to również obwód o rozmiarze minimalnym!$A$$A$$m+k$$k$$x_{i'} + x_{n+1}$$i'$$k$$m$

Dowód, że obniżka jest poprawna, nie jest tak miły. Chciałbym zobaczyć krótki dowód, że ta redukcja jest poprawna.