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

9

Позволять еf быть Nnмногочлен, заданный в виде арифметической схемы размера поли(N)(n), и разреши пзнак равно2Ω(N)p=2Ω(n) быть простым.

Можете ли вы проверить, если еf тождественно ноль ZпZp, со временем поли(N)poly(n) и вероятность ошибки 1-1/поли(N)11/poly(n)даже если степень априори не ограничена? Что, еслиеf одномерный?

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

user94741
источник
если у вас нет границ для степени, не существует ли полином, который реализует какую-то конкретную функцию?
Питер Шор
@PeterShor: OP делает есть ограничение на степень; это не может быть больше 2 до [количество ворот веf].
Я думаю, что ключевым моментом этого вопроса является то, что поле GF (p) недостаточно велико, чтобы использовать лемму Шварца – Циппеля для построения рандомизированного алгоритма полиномиального времени стандартным образом, и не достаточно мало (например, GF (2). ) использовать арифметизацию, чтобы построить сокращение от SAT стандартным способом.
Цуёси Ито
1
В одномерном случае возникает вопрос: Иксп-1xp1 водоразделы еf, который может быть проверен в большем поле, если это помогает. Не уверен, что это обобщает до многомерного.
Джеффри Ирвинг
1
@ GeoffreyIrving Спасибо! Легко ли эффективно проверить(Иксп-1)|е(xp1)|f когда еfдается как схема?
user94741

Ответы:

8

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

Учитывая главную власть Qq в двоичной и булевой схеме СC (только используя wlog а также ¬¬ ворота), мы можем построить за полиномиальное время арифметическую схему СQCq такой, что СC неудовлетворительно, если СQCq вычисляет тождественно нулевой полином над FQFq следующим образом: перевести aбab с aбab, ¬a¬a с 1-a1aи переменная Иксяxi с ИксQ-1яxq1i (который может быть выражен схемой размера О(журналQ)O(logq) с использованием повторного возведения в квадрат).

Если Qзнак равнопq=p является простым (что, я думаю, на самом деле не имеет значения) и достаточно большим, мы можем даже сделать сокращение одномерным: изменить определение СпCp так что Иксяxi переводится с полиномом ея(Икс)знак равно((Икс+я)(п-1)/2+1)п-1,

fi(x)=((x+i)(p1)/2+1)p1.
С одной стороны, ея(a){0,1}fi(a){0,1} для каждого aFпaFpследовательно, если СC неудовлетворительно, то Сп(a)знак равно0Cp(a)=0 для каждого aa, С другой стороны, предположим, чтоСC допустимо, скажем С(б1,...,бN)знак равно1C(b1,,bn)=1, где бя{0,1}bi{0,1}, Заметь ея(a)знак равно{1если a+я является квадратичным остатком (в том числе 0),0если a+я является квадратичным нерешетом.
fi(a)={10if a+i is a quadratic residue (including 0),if a+i is a quadratic nonresidue.
Таким образом, мы имеем Сп(a)знак равно1Cp(a)=1 если aFпaFp таков, что a+я является квадратичным остатком бязнак равно1
a+i is a quadratic residue bi=1
для каждого язнак равно1,...,Ni=1,,n, Из следствия 5 в Перальте следует, что такоеaa всегда существует для п(1+о(1))22NN2p(1+o(1))22nn2,
Эмиль Йержабек
источник
Одномерное сокращение фактически работает для неосновных Qq а также, до тех пор, пока это нечетно (и можно, вероятно, справиться с полномочиями 22по-другому). Вместо констант1,...,N1,,nможно взять любую фиксированную последовательность Nnотдельные элементы поля; требуетсяaa снова существует, если Q22NN2q22nn2по существу тем же аргументом, что и в статье Перальты (реальная работа заключается в ограничении Вейля на суммы символов, которое справедливо для всех конечных полей).
Эмиль Йержабек
Ах да: если Qзнак равно2К2Nq=2k2nмы можем исправить F2F2-линейно независимый {aя:язнак равно1,...,N}FQ{ai:i=1,,n}Fqи перевести Иксяxi с T(aяИкс)T(aix), где T(Икс)знак равноj<kx2jT(x)=j<kx2j is the trace of Fq/F2Fq/F2.
Emil Jeřábek