ukuran sirkuit terkecil menggunakan gerbang XOR

Misalkan kita diberi satu set n variabel boolean x_1, ..., x_n dan satu set fungsi m y_1 ... y_m di mana setiap y_i adalah XOR dari subset (diberikan) dari variabel-variabel ini. Tujuannya adalah untuk menghitung jumlah minimum operasi XOR yang perlu Anda lakukan untuk menghitung semua fungsi y_1 ... y_m ini.

Perhatikan bahwa hasil operasi XOR, katakanlah x_1 XOR x_2 dapat digunakan dalam perhitungan beberapa y_j tetapi dihitung sebagai satu. Juga, perhatikan bahwa mungkin berguna untuk menghitung XOR dari koleksi x_i yang jauh lebih besar (lebih besar dari fungsi y_i apa pun, misalnya menghitung XOR semua x_i) untuk menghitung y_i lebih efisien,

Secara ekivalen, misalkan kita memiliki matriks biner A, dan vektor X dan tujuannya adalah untuk menghitung vektor Y sedemikian sehingga AX = Y di mana semua operasi dilakukan dalam GF (2) menggunakan jumlah minimum operasi.

Bahkan ketika setiap baris A memiliki tepat k seseorang (katakanlah k = 3) menarik. Adakah yang tahu tentang kompleksitas (kekerasan perkiraan) untuk pertanyaan ini?

Mohammad Salavatiopur

Ini NP-hard. Lihat: Joan Boyar, Philip Matthews, René Peralta. Teknik Minimisasi Logika dengan Aplikasi untuk Kriptologi. http://link.springer.com/article/10.1007/s00145-012-9124-7

Pengurangan dari Vertex Cover dan sangat bagus.

Diberi grafik dengan m = | E | , Mendefinisikan m × ( n + 1 ) matriks A sebagai: A [ i , j ] = 1 jika j < n + 1 ] = 1 . Dengan kata lain, diberikan n + 1 variabel x 1 , ... $(\{1,\ldots,n\},E)$$m=|E|$$m \times (n+1)$$A$$A[i,j] = 1$ dan ( i , j ) ∈ E , dan A [ i , $j < n+1$$(i,j) \in E$$A[i,n+1] = 1$$n+1$ kita ingin menghitung$x_1,\ldots,x_{n+1}$$m$ linear bentuk untuk semua ( i , j ) ∈ E .$x_i+x_j+x_{n+1}$$(i,j) \in E$

Sedikit pemikiran menunjukkan bahwa ada sirkuit XOR untuk dengan gerbang fan-in dua menghitung transformasi linear A dengan hanya gerbang m + k , di mana k adalah penutup simpul optimal untuk grafik. (Pertama menghitung x i ' + x n + 1 untuk semua i ' di penutup vertex, menggunakan k operasi. Bentuk linear kemudian semua dihitung dalam m operasi yang lebih.) Ternyata ini juga merupakan rangkaian ukuran minimum!$A$$A$$m+k$$k$$x_{i'} + x_{n+1}$$i'$$k$$m$

Bukti bahwa pengurangan itu benar tidak begitu baik. Saya ingin melihat bukti singkat bahwa pengurangan ini benar.