¿Evaluar la multilinealización de un circuito aritmético?

Deje que un polinomio multivariable con coeficientes más de un campo . El multilinearization de , denotada por , es el resultado de sustituir repetidamente cada con por . El resultado es obviamente un polinomio multilineal. $p(x_1,\ldots,x_n)$ $F$ $p$ $\hat{p}$ $x_i^d$ $d > 1$ $x_i$

Considere el siguiente problema: dado un circuito aritmético más de y de campo dado elementos , calcular . $C(x_1,\ldots,x_n)$ $F$ $a_1,\ldots,a_n$ $\hat{C}(a_1,\ldots,a_n)$

Pregunta: Suponiendo que la aritmética de campo se pueda hacer en unidad de tiempo, ¿existe un algoritmo de tiempo polinómico para esto? Más adelante: también me interesaría el caso especial en el que es en realidad una fórmula (un circuito de abanico ). $C$ $1$

cc.complexity-theory polynomials Slimton
fuente

¿Por qué sería equivalente a calcular la salida de un circuito cerrado? El problema al que me enfrento es que el circuito puede tener rutas disjuntas desde una entrada

a varios nodos de multiplicación internos, y evaluar cada uno de esos nodos de multiplicación internos requeriría reemplazar

por

en una ruta y por

en la otra . En un circuito con un número exponencial de rutas, parece que hay un número exponencial de casos para atender.

x_{i}

$x_i$

x_{i}

$x_i$

a_{i}

$a_i$

1

$1$

Slimton

@Kaveh: No lo entiendo. Mira el circuito

. Si simplemente reemplaza el nodo de entrada

por un nodo con valor

y evalúa de la manera estándar, terminará devolviendo

lugar de

. Modelo de computación: solo tiempo polinómico normal en máquinas Turing. Piense en el campo como

para la concreción, si lo desea.

(x * x)

$(x * x)$

x

$x$

a

$a$

a^{2}

$a^2$

a

$a$

Z / 3 Z

$Z/3Z$

slimton

@Kaveh: No entiendo cómo un algoritmo de este tipo implica lo que usted dice, pero esto en realidad contradice una hipótesis común en la complejidad del circuito aritmético: que el permanente no tiene circuitos aritméticos de tamaño polivinílico (sobre campos que no sean F_2). Considere el polinomio

. La parte multilineal

de este polinomio tiene la propiedad de que su parte de mayor grado (

) es solo

p = \prod_{i} (\sum_{j} x_{i j} y_{j})

$p=\prod_i(\sum_j x_{ij} y_j)$

q

$q$

= 2 n

$=2n$

. Si hay un pequeño circuito aritmético que computa

, entonces se puede demostrar que hay un pequeño circuito aritmético que computa

r = y_{1} y_{2} \dots y_{n} P e r (x_{11}, \dots, x_{n n})

$r = y_1y_2\cdots y_n Per(x_{11},\ldots,x_{nn})$

q

$q$

r

$r$

Srikanth

@Srikanth: No vi su comentario antes de publicar mi respuesta (que resultó ser la misma construcción que dio en su comentario). Desde entonces he eliminado mi respuesta, y debes publicar tu comentario como respuesta.

Joshua Grochow

@ Joshua: No he agregado mi comentario como respuesta ya que no entiendo por qué funciona la construcción de Kaveh. Veo que el circuito aritmético calcula un polinomio que está de acuerdo con la multilinearización en todas las entradas, pero no estoy seguro de que calcule formalmente la multilinearización del polinomio dado (vea mis comentarios después de la respuesta de Kaveh). Mi construcción (y la suya) supone que la multilinealización se calcula formalmente.

Srikanth el

Respuestas:

En el caso de que el campo tenga un tamaño de al menos , creo que este problema es difícil. Más específicamente, creo que si lo anterior se puede resolver de manera eficiente para tan grande, entonces CNF-SAT tiene algoritmos aleatorios eficientes. Digamos que se nos da una fórmula CNF . Uno puede fácilmente llegar a un circuito aritmético que calcula un `` aritmetización '' de , donde el polinomio está de acuerdo con la fórmula en - entradas. Considere la multilinealización de . Tenga en cuenta que $F$ $2n$ $F$ $\varphi$ $C$ $p$ $\varphi$ $p$ $\varphi$ $0$ $1$ $q$ $p$ $q$ está de acuerdo con . $p$ y por lo tanto en $\varphi$ $\{0,1\}^n$

Afirmo que no es cero si f es satisfactoria. Claramente, si , entonces no puede ser satisfecho. Por el contrario, se puede demostrar que cualquier polinomio multilineal distinto de cero no puede desaparecer en todos los . Esto implica que un distinto de cero (y, por lo tanto, el correspondiente ) no desaparece en alguna entrada en $q$ $\varphi$ $q=0$ $\varphi$ $\{0,1\}^n$ $q$ $\varphi$ . $\{0,1\}^n$

Por lo tanto, verificar la satisfacción de es equivalente a verificar si no es cero. Por ejemplo, ahora, que podría evaluar lo largo de un gran campo . Luego, usando el Lema de Schwartz-Zippel, podríamos probar la identidad usando un algoritmo aleatorio eficiente y verificar si es el polinomio cero (el tamaño de se usa para el límite superior del error en el Lema de Schwartz-Zippel). $\varphi$ $q$ $q$ $F$ $q$ $F$

Srikanth
fuente

Me parece que F es un campo fijo porque no hay nada en la entrada que especifique F. También tenga en cuenta que la pregunta supone que las operaciones de campo toman tiempo unitario.

Kaveh

Gracias Srikanth Como Kaveh supuso que estaba realmente interesado en el caso de campo finito fijo, pero esta respuesta que me dio me ayuda a entender la pregunta un poco mejor.

Slimton

Suponga que hay un algoritmo de polytime que dado y calculó el resultado de la linealización múltiple de en . (wlog Asumiré que la salida será un vector de números binarios de bits es si f es uno). $C(\vec{x}) \in F(\vec{x})$ $\vec{a}$ $C$ $\vec{a}$ $\vec{b}$ $p$ $b_i$ $k$ $b_{i,k}$

Dado que , existe un circuito booleano polisizado que, dada la codificación del circuito aritmético, y los valores de las variables calculan la multilinealización del circuito aritmético en las entradas. Llamemos a este circuito $P \subseteq P/poly$ $M$ .

Sea un circuito aritmético arbitrario. Arregle las variables del circuito booleano que describen el circuito aritmético, por lo que tenemos un circuito booleano que calcula la multilinealización de $C$ $M$ $C$ en entradas dadas.

Podemos convertir este circuito en un circuito aritmético sobre al observar que es para todos los valores, pero por lo que primero eleva todas las entradas a la potencia . Reemplazar cada puerta por multiplicación , cada puerta por y cada puerta por . $F_p$ $x^{p-1}$ $1$ $0$ $p-1$ $f \land g$ $f.g$ $f \lor g$ $f+g-f.g$ $\lnot f$ $1-f$

Por el supuesto que hicimos anteriormente sobre el formato de la salida, podemos convertir la salida de binario a valores sobre . Tome la salida para y combínelos para obtener $F_p$ $b_i$ $\sum_{0 \leq k \leq p-1}{kb_{i,k}}$ .

También podemos convertir la entrada dada como valores sobre en forma binaria ya que hay polinomios que pasan por cualquier número finito de puntos. Por ejemplo, si estamos trabajando en , considere los polinomios y que dan el primer y el segundo bit de la entrada . $F_p$ $\bmod 3$ $2x(x+1)$ $2x(x+2)$ $x \in F_3$

La combinación de estos tenemos un circuito aritmético sobre cálculo de la multi-linealización de con polynomail tamaño en el tamaño de . $F_p$ $C$ $C$

Kaveh
fuente

It is not clear to me why the arithmetic circuit you have described computes the multilinearization of

C

$C$ , or indeed even a multilinear polynomial. I am only able to see that the arithmetic circuit computes some polynomial that agrees with the multilinearization of

C

$C$ on

0

$0$ -

1

$1$ inputs.

Srikanth

@Srikanth: the arithmetic version of the boolean circuit

M

$M$ (with some inputs fixed) computes the multilinear version of

C

$C$ , it doesn't need to be a multilinear. Then the only problem is that input/output are in binary not values over

F_{p}

$F_p$ , so I just need to fix the encoding for input/output from binary to original input and output values. The resulting circuit is an arithmetic circuit that gets the values for variables of

C

$C$ , encodes them in binary, computes the value of the multilinearization of

C

$C$ over those inputs and output the answer in binary, and then translate them back to

F_{p}

$F_p$ .

Kaveh

[continued] The result it is an arithmetic circuit with the same variables that

C

$C$ has, and with the same outputs, and it is computing the multilinearization of

C

$C$ .

Kaveh

@Kaveh: Have you assumed that the input to the boolean circuit

M

$M$ is of the same form as the output of

M

$M$ ? In any case, I am still not convinced. It is perfectly possible for an arithmetic circuit to compute a polynomial

f

$f$ that agrees with a polynomial

g

$g$ at all inputs from the field and yet

f \neq g

$f\neq g$ . For example, the polynomial

x^{p}

$x^p$ agrees with

x

$x$ at all inputs, and yet they are not equal as polynomials. How do you know that the circuit

M

$M$ is not simply computing a non-multilinear polynomial that agrees with the multilinearization of

C

$C$ at all inputs?

Srikanth

@Srikanth: I have described the form of input and output in my answer. The input to

M

$M$ is in binary, the output of

M

$M$ is in the form stated above. I haven't said that it is multilinear, I have only said that it computes the multilinearization of the $C$ .

Kaveh