Évaluer le circuit booléen sur un lot d'entrées similaires

Supposons que j'ai un circuit booléen qui calcule une fonction f : { 0 , 1 } n → { 0 , 1 } . Supposons que le circuit est composé de portes ET, OU et NON avec au plus fan-in et fan-out 2.$C$$f:\{0,1\}^n \to \{0,1\}$

Soit une entrée donnée. Étant donné C et x , je veux évaluer C sur les n entrées qui diffèrent de x dans une position de bit unique, c'est-à-dire calculer les n valeurs C ( x 1 ) , C ( x 2 ) , … , C ( x n ) où x i est identique à x sauf que son $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$e bit est retourné.

Existe-t-il un moyen de le faire plus efficace qu'une évaluation indépendante de n fois sur les n différentes entrées?$C$ $n$$n$

Supposons que contient m portes. Ensuite, l'évaluation indépendante de C sur toutes les n entrées prendra du temps O ( m n ) . Existe-t-il un moyen de calculer C ( x 1 ) , C ( x 2 ) , … , C ( x n ) en temps o ( m n ) ?$C$$m$$C$$n$$O(mn)$$C(x^1),C(x^2),\dots,C(x^n)$$o(mn)$

Contexte optionnel: Si nous avions un circuit arithmétique (dont les portes sont la multiplication, l'addition et la négation) sur , alors il serait possible de calculer les n dérivées directionnelles ∂ $\mathbb{R}$$n$en tempsO(m). Fondamentalement, nous pourrions utiliser des méthodes standard pour le calcul du gradient (règle de rétropropagation / chaîne), en tempsO(m). Cela fonctionne parce que la fonction correspondante est continue et différenciable. Je me demande si quelque chose de similaire peut être fait pour les circuits booléens. Les circuits booléens ne sont pas continus et différenciables, vous ne pouvez donc pas faire la même astuce, mais peut-être existe-t-il une autre technique intelligente que l'on peut utiliser? Peut-être une sorte de truc de Fourier, ou quelque chose?${\partial f \over \partial x_i}(x)$$O(m)$$O(m)$

(Question variante: si nous avons des portes booléennes avec fan-in illimité et fan-out borné, pouvez-vous faire mieux asymptotiquement que d'évaluer n fois?)$C$ $n$

Je considère qu'il est peu probable qu'une telle astuce soit facile à trouver et / ou vous fournisse des gains importants, car elle donnerait des algorithmes de satisfiabilité non triviaux. Voici comment:

$C$$N$$x_0, \ldots, x_{N-1}$$C$$\tilde{O}(N\cdot|C|)$$C$$C'$$|C| + \tilde{O}(Nn)$$0^i10^{N-1-i}$$C(x_{i})$$0^i10^{N-1-i}$$x_i$$C$

$\tilde{O}(|C|^{2-\epsilon} + (N\cdot|C|)^{1-\epsilon/2} + N^{2-\epsilon})$$\epsilon > 0$$C$$C$$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|))$