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?)

— DW
źródło

Ponieważ Andrew dość dobrze odpowiedział na twoje pytanie, zostawię komentarz. Gdyby

m

$m$ jest duży (jak

O (2^{n} / n)

$O(2^n/n)$ ) i oceniasz

C

$C$ na wielu wejściach (do

2^{o (n / \log n)}

$2^{o(n/\log n)}$ ), to jest

C^{'}

$C'$ tylko wielkości

O (2^{n} / n)

$O(2^n/n)$ który może ocenić

C

$C$ na każdym

m

$m$ wejścia. (W literaturze problem nazywany jest również „masową produkcją”). Zobacz Uhlig, „O syntezie schematów samokorekty z elementów funkcjonalnych z niewielką liczbą wiarygodnych elementów”. Math.Notes Acad.Sci. ZSRR 15, 558--562. Tak więc w niektórych przypadkach możesz zrobić lepiej z nierównomiernością.

— Ryan Williams,

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|))$ .

— Andrew Morgan
źródło