Рандомизированное тестирование идентичности для полиномов высокой степени?

Позволять $f$ быть $n$многочлен, заданный в виде арифметической схемы размера поли$(n)$, и разреши $p = 2^{\Omega(n)}$ быть простым.

Можете ли вы проверить, если $f$ тождественно ноль $\mathbb{Z}_p$, со временем $\mbox{poly}(n)$ и вероятность ошибки $\leq 1-1/\mbox{poly}(n)$даже если степень априори не ограничена? Что, если$f$ одномерный?

Обратите внимание, что вы можете эффективно проверить, если $f$тождественно равен нулю как формальное выражение , применяя Шварца-Циппеля над полем размера, скажем$2^{2|f|}$потому что максимальная степень $f$ является $2^{|f|}$,

Мне не совсем понятно, что является причиной проблемы и как вы применяете ограничение $p=2^{\Omega(n)}$однако при любой разумной формулировке ответ будет отрицательным для многомерных полиномов, если только NP = RP из-за приведенного ниже сокращения.

Учитывая главную власть $q$ в двоичной и булевой схеме $C$ (только используя wlog $\land$ а также $\neg$ ворота), мы можем построить за полиномиальное время арифметическую схему $C_q$ такой, что $C$ неудовлетворительно, если $C_q$ вычисляет тождественно нулевой полином над $\mathbb F_q$ следующим образом: перевести $a\land b$ с $ab$, $\neg a$ с $1-a$и переменная $x_i$ с $x_i^{q-1}$ (который может быть выражен схемой размера $O(\log q)$ с использованием повторного возведения в квадрат).

Если $q=p$ является простым (что, я думаю, на самом деле не имеет значения) и достаточно большим, мы можем даже сделать сокращение одномерным: изменить определение $C_p$ так что $x_i$ переводится с полиномом

$$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$$ С одной стороны, $f_i(a)\in\{0,1\}$ для каждого $a\in\mathbb F_p$следовательно, если $C$ неудовлетворительно, то $C_p(a)=0$ для каждого $a$, С другой стороны, предположим, что$C$ допустимо, скажем $C(b_1,\dots,b_n)=1$, где $b_i\in\{0,1\}$, Заметь $$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$ если $a\in\mathbb F_p$ таков, что $$a+i\text{ is a quadratic residue }\iff b_i=1$$ для каждого $i=1,\dots,n$, Из следствия 5 в Перальте следует, что такое$a$ всегда существует для $p\ge(1+o(1))2^{2n}n^2$,