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

13

Soit p(x1,,xn) 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.p^xidd>1xi

Considérons le problème suivant: étant donné un circuit arithmétique C(x1,,xn) sur F et des éléments extérieurs donné a1,,an , calculer C ( a 1 , ... , a n ) .C^(a1,,an)

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

slimton
la source
1
Pourquoi serait-ce équivalent à calculer la sortie d'un circuit fermé? Le problème auquel je suis confronté est que le circuit peut avoir des chemins disjoints d'une entrée à plusieurs nœuds de multiplication internes, et évaluer chacun de ces nœuds de multiplication internes nécessiterait de remplacer x i par un i dans un chemin et par 1 dans l'autre . Dans un circuit avec un nombre exponentiel de chemins, il semble qu'il y ait un nombre exponentiel de cas à prendre en charge. xixiai1
slimton
2
@Kaveh: Je ne comprends pas. Regardez le circuit . Si vous remplacez simplement le nœud d'entrée x par un nœud de valeur a et évaluez de la manière standard, vous finissez par renvoyer un 2 au lieu d' un . Modèle de calcul: temps polynomial juste normal sur les machines de Turing. Pensez au domaine comme étant Z / 3 Z pour le concret, si vous voulez. (xx)xaa2aZ/3Z
slimton
2
@Kaveh: Je ne comprends pas comment un tel algorithme implique ce que vous dites, mais cela contredit en effet une hypothèse courante dans la complexité des circuits arithmétiques: que le permanent n'a pas de circuits arithmétiques de taille poly (sur des champs autres que F_2). Considérons le polynôme . La partie multilinéaire q de ce polynôme a la propriété que sa partie de degré le plus élevé ( = 2 n ) est juste r = y 1 y 2y n P e r ( xp=i(jxijyj)q=2n. S'il existe un petit circuit arithmétique calculantq, alors on peut montrer qu'il existe un petit circuit arithmétique calculantr. r=y1y2ynPer(x11,,xnn)qr
Srikanth
1
@Srikanth: Je n'ai pas vu votre commentaire avant de poster ma réponse (qui s'est avérée être la même construction que vous avez donnée dans votre commentaire). J'ai depuis supprimé ma réponse, et vous devriez poster votre commentaire comme réponse.
Joshua Grochow
2
@Joshua: Je n'ai pas ajouté mon commentaire comme réponse car je ne comprends pas pourquoi la construction de Kaveh fonctionne. Je vois que le circuit arithmétique calcule un polynôme qui est d'accord avec la multilinéarisation à toutes les entrées, mais je ne suis pas sûr qu'il calcule formellement la multilinéarisation du polynôme donné (voir mes commentaires après la réponse de Kaveh). Ma construction (et la vôtre) suppose que la multilinéarisation est calculée formellement.
Srikanth

Réponses:

12

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 qF2nFφCpφpφ01qpqest d'accord avec et donc φ sur { 0 , 1 } n .pφ{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φq=0φ{0,1}nqφ{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).φqqFqF

Srikanth
la source
Il me semble que F est un champ fixe car il n'y a rien dans l'entrée qui spécifie F. Notez également que la question suppose que les opérations sur le terrain prennent du temps unitaire.
Kaveh
Merci Srikanth. Comme Kaveh l'a deviné, j'étais effectivement intéressé par le cas du champ fini fixe, mais cette réponse que vous avez donnée m'aide à mieux comprendre la question.
slimton
3

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(x)F(x)aCabpbikbi,k

Since PP/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 Fp by noting that xp1 is 1 for all values but 0 so first raise all inputs to the power p1. Replace each fg gate by multiplication f.g, each fg gate by f+gf.g and each ¬f gate by 1f.

By the assumption we made above about the format of the output, we can turn the output from binary to values over Fp. Take the output for bi and combine them to get 0kp1kbi,k.

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

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

Kaveh
la source
2
It is not clear to me why the arithmetic circuit you have described computes the multilinearization of 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 on 0-1 inputs.
Srikanth
@Srikanth: the arithmetic version of the boolean circuit M (with some inputs fixed) computes the multilinear version of C, it doesn't need to be a multilinear. Then the only problem is that input/output are in binary not values over Fp, 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, encodes them in binary, computes the value of the multilinearization of C over those inputs and output the answer in binary, and then translate them back to Fp.
Kaveh
[continued] The result it is an arithmetic circuit with the same variables that C has, and with the same outputs, and it is computing the multilinearization of C.
Kaveh
2
@Kaveh: Have you assumed that the input to the boolean circuit M is of the same form as the output of M? In any case, I am still not convinced. It is perfectly possible for an arithmetic circuit to compute a polynomial f that agrees with a polynomial g at all inputs from the field and yet fg. For example, the polynomial xp agrees with x at all inputs, and yet they are not equal as polynomials. How do you know that the circuit M is not simply computing a non-multilinear polynomial that agrees with the multilinearization of C at all inputs?
Srikanth
@Srikanth: I have described the form of input and output in my answer. The input to M is in binary, the output of 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