Evaluar circuito booleano en lote de entradas similares

Supongamos que tengo un circuito booleano que calcula alguna función f : { 0 , 1 } n → { 0 , 1 } . Suponga que el circuito se compone de AND, OR y NO compuertas con entrada y salida de ventilador como máximo 2.$C$$f:\{0,1\}^n \to \{0,1\}$

Sea una entrada dada. Dado C y x , quiero evaluar C en las n entradas que difieren de x en una posición de un solo bit, es decir, para calcular los n valores C ( x 1 ) , C ( x 2 ) , ... , C ( x n ) donde x i es lo mismo que x excepto que es $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$El bit está volteado.

¿Hay alguna manera de hacer esto que sea más eficiente que evaluar independientemente n veces en las n entradas diferentes?$C$ $n$$n$

Suponga que contiene m puertas. Luego, evaluar independientemente C en todas las n entradas llevará tiempo O ( m n ) . ¿Hay alguna manera de calcular C ( x 1 ) , C ( x 2 ) , ... , C ( x n ) en el tiempo o ( m n ) ?$C$$m$$C$$n$$O(mn)$$C(x^1),C(x^2),\dots,C(x^n)$$o(mn)$

Contexto opcional: si tuviéramos un circuito aritmético (cuyas puertas son multiplicación, suma y negación) sobre , entonces sería posible calcular las n derivadas direccionales ∂ $\mathbb{R}$$n$enO(m)tiempo. Básicamente, podríamos usar métodos estándar para el cálculo del gradiente (regla de propagación hacia atrás / cadena), en el tiempoO(m). Eso funciona porque la función correspondiente es continua y diferenciable. Me pregunto si se puede hacer algo similar para los circuitos booleanos. Los circuitos booleanos no son continuos y diferenciables, por lo que no puedes hacer el mismo truco, pero ¿quizás hay alguna otra técnica inteligente que puedas usar? ¿Tal vez algún tipo de truco de Fourier, o algo así?${\partial f \over \partial x_i}(x)$$O(m)$$O(m)$

(Pregunta variante: si tenemos puertas booleanas con entrada y salida sin límites, ¿puede hacerlo asintóticamente mejor que evaluar n veces?)$C$ $n$

Consideraría poco probable que tal truco sea fácil de encontrar y / o le brinde ganancias significativas, ya que daría algoritmos de satisfacción no triviales. Así es cómo:

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