Évaluer la multilinéarisation d'un circuit arithmétique?

Soit $p(x_1,\ldots,x_n)$ un polynôme à plusieurs variables avec des coefficients sur un champ $F$ . Le multilinearization de $p$ , noté p , est le résultat du remplacement de façon répétée chaque x ; d i avec d > 1 par x i . Le résultat est évidemment un polynôme multilinéaire.$\hat{p}$$x_i^d$$d > 1$$x_i$

Considérons le problème suivant: étant donné un circuit arithmétique $C(x_1,\ldots,x_n)$ sur $F$ et des éléments extérieurs donné $a_1,\ldots,a_n$ , calculer C ( a 1 , ... , a n ) .$\hat{C}(a_1,\ldots,a_n)$

Question: En supposant que l'arithmétique des champs peut être effectuée en temps unitaire, existe-t-il un algorithme polynomial pour cela? Ajouté plus tard: je serais également intéressé par le cas particulier où $C$ est en fait une formule (un circuit de fan-out $1$ ).

Dans le cas où le champ est de taille au moins 2 n , je pense que ce problème est difficile. Plus précisément, je pense que si ce qui précède peut être efficacement résolu pour F ce grand, alors CNF-SAT a des algorithmes randomisés efficaces. Supposons que l'on nous donne une formule CNF φ . On peut facilement trouver un circuit arithmétique C qui calcule une `` arithmétisation '' p de φ , où le polynôme p est d'accord avec la formule φ sur 0 - 1 entrées. Considérons la multilinéarisation q de p . Notez que $F$$2n$$F$$\varphi$$C$$p$$\varphi$$p$$\varphi$$0$$1$$q$$p$$q$est d'accord avec et donc φ sur { 0 , 1 } n .$p$$\varphi$$\{0,1\}^n$

Je prétends que est non nul ssi φ est satisfiable. Clairement, si q = 0 , alors φ ne peut pas être satisfait. Pour l'inverse, on peut montrer que tout polynôme multilinéaire non nul ne peut pas disparaître sur tout { 0 , 1 } n . Cela implique qu'un non nul q (et donc le correspondant φ ) ne disparaît pas à une entrée dans { 0 , 1 } n .$q$$\varphi$$q=0$$\varphi$$\{0,1\}^n$$q$$\varphi$$\{0,1\}^n$

Par conséquent, vérifier la satisfiabilité de équivaut à vérifier si q est différent de zéro. Dites, maintenant que nous avons pu évaluer q sur un grand champ F . Ensuite, en utilisant le lemme de Schwartz-Zippel, nous pourrions tester l'identité q en utilisant un algorithme randomisé efficace et vérifier s'il s'agit du polynôme zéro (la taille de F est utilisée pour limiter l'erreur dans le lemme de Schwartz-Zippel).$\varphi$$q$$q$$F$$q$$F$

Supposons qu'il existe un algorithme de polytime qui, étant donné et → a, a calculé le résultat de la multi-linéarisation de C sur → a . (wlog je suppose que la sortie → b sera un vecteur de nombres binaires à p bits b i est k ssi b i , k est un.)$C(\vec{x}) \in F(\vec{x})$$\vec{a}$$C$$\vec{a}$$\vec{b}$$p$$b_i$$k$$b_{i,k}$

Since $P \subseteq P/poly$, there is a polysize boolean circuit that given the encoding of the arithmetic circuit and the values for the variables computes the multi-linearization of the arithmetic circuit on the inputs. Let call this circuit $M$.

Let $C$ be an arbitrary arithmetic circuit. Fix the variables of the boolean circuit $M$ which describe the arithmetic circuit, so we have a boolean circuit computing the multi-linearization of $C$ on given inputs.

We can turn this circuit into an arithmetic circuit over $F_p$ by noting that $x^{p-1}$ is $1$ for all values but $0$ so first raise all inputs to the power $p-1$. Replace each $f \land g$ gate by multiplication $f.g$, each $f \lor g$ gate by $f+g-f.g$ and each $\lnot f$ gate by $1-f$.

By the assumption we made above about the format of the output, we can turn the output from binary to values over $F_p$. Take the output for $b_i$ and combine them to get $\sum_{0 \leq k \leq p-1}{kb_{i,k}}$.

We can also convert the input given as values over $F_p$ to binary form since there are polynomials passing through any finite number of points. E.g. if we are working in $\bmod 3$, consider the polynomials $2x(x+1)$ and $2x(x+2)$ which give the first and the second bits of the input $x \in F_3$.

Combining these we have an arithmetic circuit over $F_p$ computing the multi-linearization of $C$ with size polynomail in the size of $C$.