Mengevaluasi rangkaian boolean pada batch input yang serupa

Misalkan saya memiliki sirkuit boolean yang menghitung beberapa fungsi f : { 0 , 1 } n → { 0 , 1 } . Asumsikan sirkuit terdiri dari AND, OR, dan NOT gerbang dengan fan-in dan fan-out paling banyak 2.$C$$f:\{0,1\}^n \to \{0,1\}$

Biarkan menjadi input yang diberikan. Mengingat C dan x , saya ingin mengevaluasi C pada n input yang berbeda dari x dalam posisi bit tunggal, yaitu, untuk menghitung n nilai C ( x 1 ) , C ( x 2 ) , ... , C ( x n ) di mana x i sama dengan x kecuali bahwa $x \in \{0,1\}^n$$C$$x$$C$$n$$x$$n$$C(x^1),C(x^2),\dots,C(x^n)$$x^i$$x$$i$bit th dibalik.

Apakah ada cara untuk melakukan hal ini yang lebih efisien yang independen mengevaluasi n kali pada n yang berbeda input?$C$ $n$$n$

Asumsikan mengandung m gerbang. Kemudian mengevaluasi C secara independen pada semua n input akan memakan waktu O ( m n ) . Apakah ada cara untuk menghitung C ( x 1 ) , C ( x 2 ) , ... , C ( x n ) dalam waktu o ( m n ) ?$C$$m$$C$$n$$O(mn)$$C(x^1),C(x^2),\dots,C(x^n)$$o(mn)$

Konteks opsional: Jika kita memiliki sirkuit aritmatika (yang gandanya multiplikasi, penjumlahan, dan negasi) di atas , maka akan mungkin untuk menghitung n directional derivatives ∂ $\mathbb{R}$$n$dalam waktuO(m). Pada dasarnya, kita dapat menggunakan metode standar untuk perhitungan gradien (back-propagation / aturan rantai), dalam waktuO(m). Itu bekerja karena fungsi yang sesuai kontinu dan dapat dibedakan. Saya bertanya-tanya apakah hal serupa dapat dilakukan untuk sirkuit boolean. Sirkuit Boolean tidak kontinu dan dapat dibedakan, jadi Anda tidak dapat melakukan trik yang sama, tetapi mungkin ada beberapa teknik pintar lain yang dapat digunakan? Mungkin semacam trik Fourier, atau semacamnya?${\partial f \over \partial x_i}(x)$$O(m)$$O(m)$

(Varian pertanyaan: jika kita memiliki gerbang boolean dengan fan-in tanpa batas dan fan-out terikat, dapatkah Anda melakukan asymptotically dengan lebih baik daripada mengevaluasi n kali?)$C$ $n$

Saya menganggap itu tidak mungkin bahwa trik seperti itu mudah ditemukan dan / atau akan memberi Anda keuntungan yang signifikan, karena akan memberikan algoritma kepuasan yang tidak trivial. Begini caranya:

Pertama-tama, sementara tampaknya lebih mudah, masalah Anda sebenarnya dapat memecahkan masalah yang lebih umum, mengingat rangkaian dan N input x 0 , ... , x N - 1 , evaluasi C pada semua input lebih cepat daripada ˜ O ( N ⋅ | C | ) waktu. Alasannya adalah bahwa kita dapat men-tweak C menjadi sirkuit C ' ukuran | C | + ˜ O ( N n ) yang, pada input $C$$N$$x_0, \ldots, x_{N-1}$$C$$\tilde{O}(N\cdot|C|)$$C$$C'$$|C| + \tilde{O}(Nn)$ , menghasilkan C ( x i ) . Pada dasarnya, kami hanya membuat tabel kecil yang mengirimkan 0 i 10 N - 1 - i untuk x i , dan kawat itu ke C .$0^i10^{N-1-i}$$C(x_{i})$$0^i10^{N-1-i}$$x_i$$C$

Algoritma nontrivial untuk evaluasi batch dari sirkuit boolean kemudian dapat digunakan untuk membuat algoritma kepuasan yang cepat. Berikut adalah contoh dalam kasus sederhana di mana kita mengira kita memiliki algoritma yang melakukan evaluasi dalam waktu untuk setiap konstanta ϵ > 0 . Pada input sirkuit C , kita dapat memutuskan kepuasan dengan memperluas C ke sirkuit $\tilde{O}(|C|^{2-\epsilon} + (N\cdot|C|)^{1-\epsilon/2} + N^{2-\epsilon})$$\epsilon > 0$$C$$C$ Ukuran 2 n / 2 ⋅ | C | yang hanya OR atas semua pilihan yang mungkin dariinput n / 2 pertamake C (membiarkan input lain bebas). Kami kemudian melakukan batch-evaluasi C ′ pada semuainput 2 n / 2-nya . Hasil akhirnya adalah bahwa kami menemukan tugas yang memuaskan untuk C ′ jika C memuaskan. Waktu berjalan adalah ˜ O ( 2 ( n / 2 ) ( 2 - $C'$$2^{n/2}\cdot |C|$$n/2$$C$$C'$$2^{n/2}$$C'$$C$.$\tilde{O}(2^{(n/2)(2-\epsilon)}\cdot |C|^{2-\epsilon}) = \tilde{O}(2^{n(1-\epsilon/2)}\cdot \textrm{poly}(|C|))$