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

Sei ein variables Polynom, das als arithmetische Schaltung der Größe poly , und sei eine Primzahl. $f$ $n$ $(n)$ $p = 2^{\Omega(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? $f$ $\mathbb{Z}_p$ $\mbox{poly}(n)$ $\leq 1-1/\mbox{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$ $2^{2|f|}$ $f$ $2^{|f|}$

polynomials arithmetic-circuits 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 sein

f

$\hspace{.04 in}f\hspace{.02 in}$ ].

$\;\;\;\;$

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

Im univariaten Fall wird gefragt, ob

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.

x^{p} - 1

$x^p-1$

f

$f$

Geoffrey Irving

@GeoffreyIrving Danke! Ist es einfach, effizient zu überprüfen

wenn

als Schaltung gegeben ist?

(x^{p} - 1) | f

$(x^p - 1) | f$

f

$f$

user94741

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^{\Omega(n)}$

Bei einer Primzahl in binärer und einer booleschen Schaltung (wlog unter Verwendung von nur und Gates) können wir in Polynomzeit eine arithmetische Schaltung so konstruieren, dass unbefriedigend ist, wenn ein Polynom mit identischer Null über as berechnet folgt: übersetze mit , mit und eine Variable mit $q$ $C$ $\land$ $\neg$ $C_q$ $C$ $C_q$ $\mathbb F_q$ $a\land b$ $ab$ $\neg a$ $1-a$ $x_i$ $x_i^{q-1}$ (was durch eine Schaltung der Größe durch wiederholtes Quadrieren ausgedrückt werden kann ). $O(\log q)$

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 so, dass mit dem Polynom Einerseits ist $q=p$ $C_p$ $x_i$

f_{ich} (x) = ((x + ich)^{(p - - 1) /. 2} + 1)^{p - - 1} .

$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$

für jedes

, wenn also

erfüllbar ist, dann ist

für jedes

. Nehmen wirandererseits an, dass

erfüllbar ist, sagen wir

, wobei

. Beachten Sie, dass

f_{i} (a) \in {0, 1}

$f_i(a)\in\{0,1\}$

a \in F_{p}

$a\in\mathbb F_p$

C

$C$

C_{p} (a) = 0

$C_p(a)=0$

a

$a$

C

$C$

C (b_{1}, \dots, b_{n}) = 1

$C(b_1,\dots,b_n)=1$

b_{i} \in {0, 1}

$b_i\in\{0,1\}$

Wir haben also

wenn

ist, dass

f_{ich} (ein) = {\begin{cases} 1 & wenn ein + ich ist ein quadratischer Rest (einschließlich 0), \\ 0 & wenn ein + ich ist ein quadratischer Rückstand. \end{cases}

$f_i(a)=\begin{cases}1&\text{if $a+i$ is a quadratic residue (including $0$),}\\ 0&\text{if $a+i$ is a quadratic nonresidue.}\end{cases}$

C_{p} (a) = 1

$C_p(a)=1$

a \in F_{p}

$a\in\mathbb F_p$

für jedes

. Corollary 5 inPeraltaimpliziertdass solche

existiert immer für

ein + ich ist ein quadratischer Rest ⟺ b_{ich} = 1

$a+i\text{ is a quadratic residue }\iff b_i=1$

i = 1, \dots, n

$i=1,\dots,n$

a

$a$

p \geq (1 + o (1)) 2^{2 n} n^{2}

$p\ge(1+o(1))2^{2n}n^2$

Emil Jeřábek
quelle

Die univariate Reduktion funktioniert auch für Nicht-Prim-

, solange sie ungerade ist (und man kann wahrscheinlich Potenzen von

auf andere Weise handhaben ). Anstelle der Konstanten

kann man eine beliebige feste Folge von

verschiedenen Elementen des Feldes nehmen; Das erforderliche

existiert wieder, wenn

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

q

$q$

2

$2$

1, \dots, n

$1,\dots,n$

n

$n$

a

$a$

q \geq 2^{2 n} n^{2}

$q\ge2^{2n}n^2$

Emil Jeřábek

Ah, ja: Wenn

, können wir

-linear unabhängig

fixieren und

mit

, wobei

ist die Spur von

q = 2^{k} \geq 2^{n}

$q=2^k\ge2^n$

F_{2}

$\mathbb F_2$

{a_{i} : i = 1, \dots, n} \subseteq F_{q}

$\{a_i:i=1,\dots,n\}\subseteq\mathbb F_q$

x_{i}

$x_i$

T (a_{i} x)

$T(a_ix)$

T (x) = \sum_{j < k} x^{2^{j}}

$T(x)=\sum_{j<k}x^{2^j}$

F_{q} / F_{2}

$\mathbb F_q/\mathbb F_2$

Emil Jeřábek

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

Antworten: