Oceń obwód logiczny na partii podobnych danych wejściowych

Załóżmy, że mam obwód boolowski $C$ która oblicza jakąś funkcję $f:\{0,1\}^n \to \{0,1\}$. Załóżmy, że obwód składa się z AND, OR i NOT bramek z wachlarzem i wachlowaniem co najwyżej 2.

Pozwolić $x \in \{0,1\}^n$być danym wkładem. Dany$C$ i $x$, Chcę ocenić $C$ na $n$ dane wejściowe, które różnią się od $x$ w pozycji pojedynczego bitu, tj. do obliczenia $n$ wartości $C(x^1),C(x^2),\dots,C(x^n)$ gdzie $x^i$ jest taki sam jak $x$ oprócz tego, że to $i$bit jest odwrócony.

Czy istnieje sposób, aby to zrobić, który jest bardziej wydajny niż niezależna ocena $C$ $n$ razy na $n$ różne dane wejściowe?

Założyć $C$ zawiera $m$bramy Następnie samodzielnie ocenia$C$ na wszystkich $n$ wejścia zajmie $O(mn)$czas. Czy istnieje sposób na obliczenie$C(x^1),C(x^2),\dots,C(x^n)$ w $o(mn)$ czas?

Kontekst opcjonalny: Gdybyśmy mieli obwód arytmetyczny (którego bramkami jest mnożenie, dodawanie i negowanie) ponad$\mathbb{R}$, wówczas można obliczyć $n$ pochodne kierunkowe ${\partial f \over \partial x_i}(x)$ w $O(m)$czas. Zasadniczo moglibyśmy użyć standardowych metod obliczania gradientu (wsteczna propagacja / reguła łańcuchowa) w$O(m)$czas. Działa to, ponieważ odpowiednia funkcja jest ciągła i można ją rozróżnić. Zastanawiam się, czy coś podobnego można zrobić dla obwodów boolowskich. Obwody boolowskie nie są ciągłe i różnicowalne, więc nie możesz zrobić tej samej sztuczki, ale może jest jakaś inna sprytna technika, której można użyć? Może jakiś trik Fouriera lub coś takiego?

(Pytanie wariantowe: jeśli mamy bramki typu boolean z nieograniczonym wachlarzem i ograniczonym wachlarzem, czy można zrobić asymptotycznie lepiej niż oceniać $C$ $n$ czasy?)

Uważam, że jest mało prawdopodobne, że taka sztuczka jest łatwa do znalezienia i / lub da ci znaczące korzyści, ponieważ dałaby niełatwe algorytmy satysfakcji. Oto jak:

Przede wszystkim, choć pozornie łatwiejszy, twój problem może faktycznie rozwiązać bardziej ogólny problem, biorąc pod uwagę obwód $C$ i $N$ wejścia $x_0, \ldots, x_{N-1}$, oceń $C$ przy wszystkich wejściach szybciej niż $\tilde{O}(N\cdot|C|)$czas. Powodem jest to, że możemy dostosować$C$ w obwód $C'$ wielkościowy $|C| + \tilde{O}(Nn)$ który na wejściu $0^i10^{N-1-i}$, wyjścia $C(x_{i})$. Zasadniczo tworzymy małą tabelę odnośników, która wysyła$0^i10^{N-1-i}$ do $x_i$i podłącz go $C$.

Nietrywialne algorytmy oceny partii obwodów boolowskich mogą być następnie wykorzystane do stworzenia szybkich algorytmów satysfakcji. Oto przykład w prostym przypadku, w którym przypuszczamy, że mamy algorytm dokonujący oceny na czas$\tilde{O}(|C|^{2-\epsilon} + (N\cdot|C|)^{1-\epsilon/2} + N^{2-\epsilon})$ dla dowolnej stałej $\epsilon > 0$. Na wejściu obwodu$C$, możemy zadecydować o satysfakcji poprzez rozszerzenie $C$ w obwód $C'$ wielkościowy $2^{n/2}\cdot |C|$ który jest po prostu OR dla wszystkich możliwych wyborów pierwszego $n/2$ dane wejściowe do $C$(pozostawiając inne wejścia wolne). Następnie oceniamy partię$C'$ na wszystkich jego $2^{n/2}$wejścia. W rezultacie znajdujemy satysfakcjonujące zadanie$C'$ iff $C$jest zadowalający. Czas działania wynosi$\tilde{O}(2^{(n/2)(2-\epsilon)}\cdot |C|^{2-\epsilon}) = \tilde{O}(2^{n(1-\epsilon/2)}\cdot \textrm{poly}(|C|))$.