Bewertung der Multilinearisierung einer Rechenschaltung?

13

Lassen p ( x 1 , ... , x n )p(x1,,xn) mit Koeffizienten über ein Feld ein multivariate Polynom FF . Die multilinearization von pp , bezeichnet durch p , das Ergebnis des wiederholten Ersetzen jedes x d i mit d > 1 von x i . Das Ergebnis ist offensichtlich ein multilineares Polynom.p^xdid>1xi

Betrachten wir das folgende Problem: Da eine arithmetische Schaltung C ( x 1 , ... , x n )C(x1,,xn) über FF und gegebenen Feldelemente a 1 , ... , a na1,,an , compute C ( a 1 , ... , a n ) .C^(a1,,an)

Frage: Unter der Annahme, dass Feldarithmetik in Zeiteinheiten durchgeführt werden kann, gibt es dafür einen Polynom-Zeit-Algorithmus? Später hinzugefügt: Mich würde auch der Sonderfall interessieren, bei dem CC eigentlich eine Formel ist (eine Schaltung von Fan-Out 11 ).

Slimton
quelle
1
Warum wäre es gleichbedeutend mit der Berechnung des Ausgangs eines geschlossenen Stromkreises? Das Problem, dem ich gegenüberstehe, besteht darin, dass die Schaltung disjunkte Pfade von einem Eingang x i zu mehreren internen Multiplikationsknoten aufweisen kann, und das Bewerten jedes dieser internen Multiplikationsknoten das Ersetzen von x i durch ein i in einem Pfad und durch 1 in dem anderen erfordern würde . In einer Schaltung mit einer exponentiellen Anzahl von Pfaden scheint es eine exponentielle Anzahl von Fällen zu geben, die behandelt werden müssen. xixicheinich1
Slimton
2
@Kaveh: Ich verstehe es nicht. Sieh Dir die Schaltung an ( x x ) . Wenn Sie einfach den Knoten von Eingabe x durch einen Knoten mit dem Wert a ersetzen und wie üblich auswerten, erhalten Sie eine 2 anstelle von a . Rechenmodell: Nur normale Polynomzeit auf Turing-Maschinen. Stellen Sie sich das Feld als Z / 3 Z für die Konkretheit vor, wenn Sie möchten. ( x x )xeinein2einZ/ 3Z
Slimton
2
@Kaveh: Ich verstehe nicht, wie ein solcher Algorithmus impliziert, was Sie sagen, aber dies widerspricht in der Tat einer verbreiteten Hypothese in Bezug auf die Komplexität von Rechenschaltungen: Die Permanente hat keine polygroßen Rechenschaltungen (über andere Felder als F_2). Betrachten Sie das Polynom p = i ( j x i j y j ) . Der mehrlineare Teil q dieses Polynoms hat die Eigenschaft, dass sein höchstgradiger ( = 2 n ) Teil nur r = y 1 y 2y n P e r ( x istp=i(jxijyj)q=2n11 ,, x n n ). Wenn es eine kleine Rechenschaltung gibt, dieqberechnet, kann man zeigen, dass es eine kleine Rechenschaltung gibt, dierberechnet. r=y1y2ynPer(x11,,xnn)qr
Srikanth
1
@Srikanth: Ich habe Ihren Kommentar vor dem Posten meiner Antwort nicht gesehen (was sich als dieselbe Konstruktion herausstellte, die Sie in Ihrem Kommentar angegeben haben). Ich habe meine Antwort inzwischen gelöscht und Sie sollten Ihren Kommentar als Antwort posten.
Joshua Grochow
2
@Joshua: Ich habe meinen Kommentar nicht als Antwort hinzugefügt, da ich nicht verstehe, warum Kavehs Bau funktioniert. Ich sehe, dass die arithmetische Schaltung ein Polynom berechnet, das mit der Multilinearisierung bei allen Eingaben übereinstimmt, aber ich bin nicht sicher, ob es formal die Multilinearisierung des gegebenen Polynoms berechnet (siehe meine Kommentare nach Kavehs Antwort). Meine (und Ihre) Konstruktion geht davon aus, dass die Multilinearisierung formal berechnet wird.
Srikanth

Antworten:

12

Für den Fall, dass das Feld F mindestens 2 n groß ist , halte ich dieses Problem für schwierig. Insbesondere denke ich, dass CNF-SAT effiziente randomisierte Algorithmen hat , wenn das Obige effizient für F dieser Größe gelöst werden kann. Nehmen wir an, wir erhalten eine CNF-Formel φ . Man kann sich leicht mit einer arithmetischen Schaltung kommen C , die eine `` Arithmetisierung ‚‘ berechnet p von φ , wobei das Polynom p mit der Formel übereinstimmt φ auf 0 - 1 Eingänge. Betrachten Sie die Multilinearisierung q von p . Beachten Sie, dass qF2nFφCpφpφ01qpqstimmt mit p überein und daher φ auf { 0 , 1 } n .pφ{0,1}n

Ich behaupte, dass q nicht Null ist, wenn φ erfüllbar ist. Wenn q = 0 ist , kann φ natürlich nicht erfüllt werden. Umgekehrt kann man zeigen, dass ein nicht-null Multilinearpolynom nicht auf allen { 0 , 1 } n verschwinden kann . Dies impliziert, dass ein von Null verschiedenes q (und damit das entsprechende φ ) bei einer Eingabe in { 0 , 1 } n nicht verschwindet .qφq=0φ{0,1}nqφ{0,1}n

Daher ist das Prüfen der Erfüllbarkeit von φ gleichbedeutend mit dem Prüfen, ob q nicht Null ist. Sagen wir nun, wir könnten q über ein großes Feld F auswerten . Dann können wir mit dem Schwartz-Zippel-Lemma q mit einem effizienten randomisierten Algorithmus identifizieren und prüfen, ob es sich um das Nullpolynom handelt (die Größe von F wird verwendet, um den Fehler im Schwartz-Zippel-Lemma nach oben zu begrenzen).φqqFqF

Srikanth
quelle
It seems to me that F is a fixed field because there is nothing in the input that specifies F. Also note that the question assumes that field operations take unit time.
Kaveh
Thanks Srikanth. As Kaveh guessed I was indeed interested in the fixed finite field case, but this answer you gave helps me understand the question a bit better.
slimton
3

Assume that there is polytime algorithm that given C(x)F(x)C(x⃗ )F(x⃗ ) and aa⃗  computed the result of the multi-linearization of CC on aa⃗ . (w.l.o.g. I will assume that the output bb⃗  will be a vector of pp-bit binary numbers bibi is kk iff the bi,kbi,k is one.)

Since PP/polyPP/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 MM.

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

We can turn this circuit into an arithmetic circuit over FpFp by noting that xp1xp1 is 11 for all values but 00 so first raise all inputs to the power p1p1. Replace each fgfg gate by multiplication f.gf.g, each fgfg gate by f+gf.gf+gf.g and each ¬f¬f gate by 1f1f.

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

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

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

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