¿Se sabe que existen funciones con la siguiente propiedad de suma directa?

Esta pregunta puede hacerse en el marco de la complejidad del circuito de los circuitos booleanos, o en el marco de la teoría de la complejidad algebraica, o probablemente en muchos otros entornos. Es fácil mostrar, contando argumentos, que existen funciones booleanas en N entradas que requieren exponencialmente muchas puertas (aunque, por supuesto, no tenemos ningún ejemplo explícito). Supongamos que deseo evaluar la misma función M veces, para algún número entero M, en M conjuntos distintos de entradas, de modo que el número total de entradas sea MN. Es decir, sólo queremos evaluar para la misma funciónfen cada momento.$f(x_{1,1},...,x_{1,N}), f(x_{2,1},...,x_{2,N}),...,f(x_{M,1},...,x_{M,N})$$f$

La pregunta es: ¿se sabe que existe una secuencia de funciones (una función para cada N) de modo que, para cualquier N, para cualquier M, el número total de puertas requerido es al menos igual a M veces una función exponencial de ¿NORTE? El argumento de conteo simple no parece funcionar ya que queremos que este resultado se mantenga para todos los M. Uno puede encontrar análogos simples de esta pregunta en la teoría de la complejidad algebraica y otras áreas.$f$

Bueno, eso es falso: es posible evaluar M copias de CUALQUIER f usando solo compuertas O (N (M + 2 ^ N)) que pueden ser mucho menores que M * exp (N) (de hecho, obtienes amortización lineal complejidad para exponencial M). No recuerdo una referencia, pero creo que puede ser algo como lo siguiente:

Primero agregue 2 ^ N entradas ficticias que son solo constantes 0 ... 2 ^ N-1 y ahora denota la i-ésima entrada de N bits por xi (entonces para i <= 2 ^ N tenemos xi = i, y para 2 ^ N <i <= 2 ^ N + M tenemos las entradas originales). Ahora creamos un triplete para cada una de las entradas M + 2 ^ N: (i, xi, fi) donde fi es f (i) para las primeras 2 ^ N entradas (una constante que está conectada al circuito) y fi = "*" de lo contrario. Ahora clasificamos los trillizos (i, xi, fi) de acuerdo con la clave xi, y dejamos que el j'th triplete sea (i_j, x_j, f_j) a partir de esto calculamos un triplete (i_j, x_j, g_j) dejando que g_j sea f_j si f_j no es un "*" y deje que g_j sea g_ (j-1) de lo contrario. Ahora ordena los nuevos trillizos de nuevo según la clave i_j, y obtienes las respuestas correctas en los lugares correctos.

$O(2^n/n)$$m$$m$$f$$m 2^n/n$

"Redes que computan funciones booleanas para múltiples valores de entrada"

$m = 2^{o(n/\log n)}$$m$$f$$O(2^n/n)$$m = 1$

No puedo encontrar una copia no cerrada en línea, o una página de inicio para el autor, pero encontré el artículo en este procedimiento:

Complejidad de la función booleana (London Mathematical Society Lecture Note Series)

Con respecto a la complejidad algebraica, no conozco un ejemplo en el que la complejidad exponencial se reduzca a una complejidad amortizada sub-exponencial, pero al menos hay un ejemplo simple de que la complejidad de M copias disjuntas puede ser significativamente menor que M veces la complejidad de una sola copia :

Para una matriz "aleatoria" n * n A, la complejidad de la forma bilineal definida por A, (la función f_A (x, y) = xAy, donde x e y son 2 vectores de longitud n) es Omega (n ^ 2 ): esto se puede mostrar mediante un argumento de dimensión "contando", ya que necesita n ^ 2 "lugares" en el circuito para colocar constantes. Sin embargo, dados n pares diferentes de vectores (x ^ 1, y ^ 1) ... (x ^ n, y ^ n), puede colocar las x en las filas de una matriz n * n X, y de manera similar las y en las columnas de una matriz Y, y luego lea todas las respuestas x ^ iAy ^ i desde la diagonal de XAY, donde esto se calcula en n ^ 2.3 (más o menos) operaciones usando una multiplicación de matriz rápida, significativamente menor que n * n ^ 2.

Esto fue estudiado y resuelto por Wolfgang Paul, quien mostró esencialmente lo que se discute.