Avalie o circuito booleano em lotes de entradas semelhantes

Suponha que eu tenha um circuito booleano que calcule alguma função f : { 0 , 1 } n → { 0 , 1 } . Suponha que o circuito seja composto de portas AND, OR e NOT com entrada e saída de ventilador no máximo 2.$C$$f:\{0,1\}^n \to \{0,1\}$

Vamos ser um dado de entrada. Dados C e x , quero avaliar C nas n entradas que diferem de x em uma única posição de bit, ou seja, para calcular os valores n C ( x 1 ) , C ( x 2 ) , … , C ( x n ) onde x i é o mesmo que x, exceto que seu $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$o bit é invertido.

Existe uma maneira de fazer isso que seja mais eficiente que avaliar independentemente n vezes nas n entradas diferentes?$C$ $n$$n$

Suponha contém m portões. A avaliação independente de C em todas as n entradas levará tempo O ( m n ) . Existe uma maneira de calcular C ( x 1 ) , C ( x 2 ) , … , C ( x n ) em o ( m n ) tempo?$C$$m$$C$$n$$O(mn)$$C(x^1),C(x^2),\dots,C(x^n)$$o(mn)$

Contexto opcional: se tivéssemos um circuito aritmético (cujas portas são multiplicação, adição e negação) sobre , seria possível calcular as n derivadas direcionais ∂ $\mathbb{R}$$n$emS(m)o tempo. Basicamente, poderíamos usar métodos padrão para o cálculo do gradiente (retropropagação / regra da cadeia), emO(m)tempo. Isso funciona porque a função correspondente é contínua e diferenciável. Gostaria de saber se algo semelhante pode ser feito para circuitos booleanos. Os circuitos booleanos não são contínuos e diferenciáveis, então você não pode fazer o mesmo truque, mas talvez haja alguma outra técnica inteligente que se possa usar? Talvez algum tipo de truque de Fourier, ou algo assim?${\partial f \over \partial x_i}(x)$$O(m)$$O(m)$

(Pergunta variante: se tivermos portões booleanos com fan-in ilimitado e fan-out limitado, você pode se sair assintoticamente melhor do que avaliar n vezes?)$C$ $n$

Eu consideraria improvável que esse truque seja fácil de encontrar e / ou lhe traga ganhos significativos, pois daria algoritmos de satisfação não triviais. Aqui está como:

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