Test d'identité aléatoire pour les polynômes de haut degré?

Soit un polynôme à variables donné comme un circuit arithmétique de taille poly , et soit un nombre premier. $f$ $n$ $(n)$ $p = 2^{\Omega(n)}$

Pouvez-vous tester si est identique à zéro sur , avec un temps et une probabilité d'erreur , même si le degré n'est pas a priori borné? Et si est univarié? $f$ $\mathbb{Z}_p$ $\mbox{poly}(n)$ $\leq 1-1/\mbox{poly}(n)$ $f$

Notez que vous pouvez tester efficacement si est identique à zéro en tant qu'expression formelle , en appliquant Schwartz-Zippel sur un champ de taille, disons , car le degré maximum de est . $f$ $2^{2|f|}$ $f$ $2^{|f|}$

polynomials arithmetic-circuits user94741
la source

si vous n'avez pas de limites sur le degré, n'y a-t-il pas un polynôme qui réalise une fonction spécifique?

Peter Shor

@PeterShor:

$\:$ L'OP n'ont une borne sur le degré; il ne peut pas y avoir plus de 2 à [le nombre de portes

f

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

$\;\;\;\;$

Je pense que le point crucial de cette question est que le champ GF (p) n'est ni assez grand pour utiliser le lemme de Schwartz – Zippel pour construire un algorithme à temps polynomial randomisé de manière standard, ni assez petit (comme GF (2) ) d'utiliser l'arithmétisation pour construire une réduction de SAT de manière standard.

Tsuyoshi Ito

x^{p} - 1

$x^p-1$

f

$f$

(x^{p} - 1) | f

$(x^p - 1) | f$

f

$f$

Réponses:

$p=2^{\Omega(n)}$

$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}$ (qui peut s'exprimer par un circuit de taille utilisant la quadrature répétée). $O(\log q)$

$q=p$ $C_p$ $x_i$

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

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

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\}$

f_{i} (a) = {\begin{cases} 1 & if a + i is a quadratic residue (including 0), \\ 0 & if a + i is a quadratic nonresidue. \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$

a + i is a quadratic residue ⟺ b_{i} = 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
la source

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$

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$