Randomizowane testy tożsamości dla wielomianów wysokiego stopnia?

Niech będzie wielomianem zmiennym podanym jako obwód arytmetyczny o rozmiarze poli i niech będzie liczbą pierwszą.$f$$n$$(n)$$p = 2^{\Omega(n)}$

Czy możesz sprawdzić, czy jest identycznie zerowe w stosunku do , z czasem i prawdopodobieństwem błędu , nawet jeśli stopień nie jest a priori ograniczone? Co jeśli jest jednoznaczny?$f$$\mathbb{Z}_p$$\mbox{poly}(n)$$\leq 1-1/\mbox{poly}(n)$$f$

Zauważ, że możesz skutecznie przetestować, czy jest identycznie zerowy jako wyrażenie formalne , stosując Schwartz-Zippel na polu wielkości powiedz , ponieważ maksymalny stopień wynosi .$f$ $2^{2|f|}$$f$$2^{|f|}$

Nie jest dla mnie do końca jasne, na czym polega problem i jak egzekwujesz ograniczenie $p=2^{\Omega(n)}$, jednak, przy jakimkolwiek rozsądnym sformułowaniu, odpowiedź brzmi „ nie” dla wielomianowych wielomianów, chyba że NP = RP, ze względu na poniższe zmniejszenie.

Biorąc pod uwagę główną moc $q$ w układzie binarnym i logicznym $C$ (wlog tylko przy użyciu $\land$ i $\neg$ bram), możemy zbudować w czasie wielomianowym obwód arytmetyczny $C_q$ takie, że $C$ jest niezadowalający iff $C_q$ oblicza identyczny zero wielomianu $\mathbb F_q$ w następujący sposób: tłumaczyć $a\land b$ z $ab$, $\neg a$ z $1-a$i zmienna $x_i$ z $x_i^{q-1}$ (co można wyrazić za pomocą obwodu wielkości $O(\log q)$ przy użyciu powtarzanego kwadratu).

Gdyby $q=p$ jest liczbą pierwszą (co, jak sądzę, nie ma znaczenia) i wystarczająco dużą, możemy nawet uczynić redukcję jednoczynnikową: zmodyfikować definicję $C_p$ po to aby $x_i$ jest tłumaczone za pomocą wielomianu

$$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$$ Z jednej strony, $f_i(a)\in\{0,1\}$ dla każdego $a\in\mathbb F_p$, stąd jeśli $C$ jest zatem niezadowalająca $C_p(a)=0$ dla każdego $a$. Z drugiej strony załóżmy, że$C$ powiedzmy, że jest zadowalający $C(b_1,\dots,b_n)=1$, gdzie $b_i\in\{0,1\}$. Zauważ, że $$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}$$ Tak więc mamy $C_p(a)=1$ gdyby $a\in\mathbb F_p$ jest taki, że $$a+i\text{ is a quadratic residue }\iff b_i=1$$ dla każdego $i=1,\dots,n$. Wniosek 5 w Peralcie implikuje, że takie$a$ zawsze istnieje dla $p\ge(1+o(1))2^{2n}n^2$.