Randomisierte Identitätsprüfung für hochgradige Polynome?

9

Sei ein variables Polynom, das als arithmetische Schaltung der Größe poly , und sei eine Primzahl.n ( n ) p = 2 Ω ( n )fn(n)p=2Ω(n)

Können Sie testen, ob über identisch ist , mit der Zeit und der Fehlerwahrscheinlichkeit , auch wenn der Grad nicht ist a priori begrenzt? Was ist, wenn univariat ist?Z p Poly ( n ) 1 - 1 / Poly ( n ) ffZ.ppoly(n)1- -1/.poly(n)f

Beachten Sie, dass Sie effizient testen können, ob als formaler Ausdruck identisch Null ist , indem Sie Schwartz-Zippel auf ein Feld mit der Größe anwenden , da der maximale Grad von beträgt .f f 2 | f |22|f|f2|f|

user94741
quelle
Wenn Sie keine Grenzen für den Grad haben, gibt es dann kein Polynom, das eine bestimmte Funktion realisiert?
Peter Shor
@ PeterShor: Das OP hat eine Grenze für den Abschluss; es kann nicht mehr als 2 bis [die Anzahl der Tore in seinf].
Ich denke, der entscheidende Punkt dieser Frage ist, dass das Feld GF (p) weder groß genug ist, um mit dem Schwartz-Zippel-Lemma einen randomisierten Polynom-Zeit-Algorithmus auf Standardweise zu konstruieren, noch klein genug (wie GF (2)). ) Arithmetisierung verwenden, um eine Reduktion aus SAT auf standardmäßige Weise zu konstruieren.
Tsuyoshi Ito
1
Im univariaten Fall wird gefragt, ob f teilt , was in einem größeren Feld überprüft werden kann, wenn dies hilft. Ich bin mir nicht sicher, ob dies auf multivariate verallgemeinert wird. xp1f
Geoffrey Irving
1
@GeoffreyIrving Danke! Ist es einfach, effizient zu überprüfen wenn f als Schaltung gegeben ist? (xp- -1)|ff
user94741

Antworten:

8

Mir ist nicht genau klar, was die Eingabe des Problems ist und wie Sie die Einschränkung . Unter jeder vernünftigen Formulierung lautet die Antwort jedoch für multivariate Polynome Nein, es sei denn, NP = RP, aufgrund der Reduktion unten.p=2Ω(n)

Bei einer Primzahl in binärer und einer booleschen Schaltung C (wlog unter Verwendung von nur und ¬ Gates) können wir in Polynomzeit eine arithmetische Schaltung C q so konstruieren, dass C unbefriedigend ist, wenn C q ein Polynom mit identischer Null über F q as berechnet folgt: übersetze a b mit a b , ¬ a mit 1 - a und eine Variable x i mit x q - 1 iqC.¬C.qC.C.qF.qeinbeinb¬ein1- -einxichxichq- -1(was durch eine Schaltung der Größe durch wiederholtes Quadrieren ausgedrückt werden kann ).Ö(Logq)

Wenn eine Primzahl ist (was meiner Meinung nach nicht wirklich wichtig ist) und ausreichend groß ist, können wir die Reduktion sogar univariat machen: Ändern Sie die Definition von C p so, dass x i mit dem Polynom f i ( x ) = (übersetzt wird) ( x + i ) ( p - 1 ) / 2 + 1 ) p - 1 . Einerseits ist f i ( a ) { 0 ,q=pC.pxich

fich(x)=((x+ich)(p- -1)/.2+1)p- -1.
für jedes a F p , wenn also C nicht erfüllbar ist, dann ist C p ( a ) = 0 für jedes a . Nehmen wirandererseits an, dass C erfüllbar ist, sagen wir C ( b 1 , , b n ) = 1 , wobei b i{ 0 , 1 } ist . Beachten Sie, dass f i ( a ) = { 1fich(ein){0,1}}einF.pC.C.p(ein)=0einC.C.(b1,,bn)=1bich{0,1}} Wir haben alsoCp(a)=1,wennaFp soist, dass a+i ein quadratischer Rest ist 
fich(ein)={1wenn ein+ich ist ein quadratischer Rest (einschließlich 0),0wenn ein+ich ist ein quadratischer Rückstand.
C.p(ein)=1einF.p für jedes i = 1 , , n . Corollary 5 inPeraltaimpliziertdass solche eine existiert immer für p ( 1 + o ( 1 ) ) 2 2 n n 2 .
ein+ich ist ein quadratischer Rest bich=1
ich=1,,neinp(1+Ö(1))22nn2
Emil Jeřábek
quelle
Die univariate Reduktion funktioniert auch für Nicht-Prim- , solange sie ungerade ist (und man kann wahrscheinlich Potenzen von 2 auf andere Weise handhaben ). Anstelle der Konstanten 1 , , n kann man eine beliebige feste Folge von n verschiedenen Elementen des Feldes nehmen; Das erforderliche a existiert wieder, wenn q 2 2 n n 2 nach im Wesentlichen demselben Argument wie in Peraltas Aufsatz (die eigentliche Arbeit ist in Weils Bindung an Zeichensummen, die für alle endlichen Felder gilt). q21,,nneinq22nn2
Emil Jeřábek
Ah, ja: Wenn , können wir F 2 -linear unabhängig { a i : i = 1 , , n } F q fixieren und x i mit T ( a i x ) übersetzen , wobei T ( x ) = j < k x 2 j ist die Spur von F q / F.q=2k2nF2{ai:i=1,,n}FqxiT(aix)T(x)=j<kx2j . Fq/F2
Emil Jeřábek