Проверка полиномиальных множителей на линейные

9

Позволять fQ[x1,x2,,xn] быть полиномом, заданным арифметической схемой C размера s, ДанныйC в качестве входных данных, есть ли детерминированный алгоритм, чтобы проверить, все ли неприводимые факторы f в Q[x1,x2,,xn]такое линейные формы? На связанной ноте, учитывая линейную формуl=i=1nlixiможем ли мы проверить детерминистически l является фактором f, Конечно, мы хотим, чтобы время выполнения было полиномиальным в обоих случаях. Под размером мы подразумеваем общий размер бита. Кроме того, можно предположить, что степеньf является полиномом в n,

Горав Джиндал
источник
Когда вы говорите "размер s«Означает ли это количество вентилей / проводов или общий размер в битах (с учетом битов, используемых для описания любых констант в схеме)?»
Джошуа Грохов
@JoshuaGrochow, да, размер здесь - размер битов.
Горав Джиндал
2
Три комментария, которые вы, вероятно, уже имели в виду, но на всякий случай: 1. Относительно полиномиального времени, алгоритмы факторизации для арифметических схем полиномиальны по размеру и степени полинома, и я не знаю алгоритмов для связанных задач, которые выполняются в Полиномиальное время только в размере. 2. Что касается детерминизма, эти алгоритмы являются рандомизированными, и детерминированные варианты становятся экспоненциальными по числу переменных. 3. Второй вопрос можно перевести в проблему PIT, поэтому ваш вопрос сводится к дерандомизации некоторого конкретного алгоритма PIT.
Бруно
Я также добавляю, что я нахожу эти проблемы очень интересными, и я хотел бы знать, что уже известно об этом!
Бруно
re PIT, проверка полиномиальной идентичности с помощью Schwartz-Zippel / wikipedia, и в этой области ведутся активные исследования. (Можно ли использовать pg PIT для разложения целых чисел, но что это за ссылка, в которой описано, как использовать ее для разложения полиномов?)
vzn

Ответы:

8

Насколько я знаю, лучший алгоритм, который мы имеем в настоящее время, чтобы проверить, если f(заданный арифметической схемой) может быть разложен на линейные факторы с помощью рандомизированного алгоритма Кальтофена (PDF), который фактически производит черные ящики для всех неприводимых факторовfи работает над любым достаточно большим полем. Фактически, эта проблема полиномиальной факторизации для общих цепей была недавно показана Коппарти, Сарафом и Шпилкой эквивалентной проблеме черного ящика-PIT для общих цепей.

Как уже упоминалось Бруно, если вы заинтересованы в проверке, данная схема делится на данную , то это сводится к конкретной проблеме PIT. Мы не знаем, как сделать это детерминистически в целом, но я знаю один особый случай, когда мы знаем, как сделать это ЯМ. Существует детерминированный многополосный алгоритм (PDF), чтобы проверить, является ли данный делит данный разреженный полином f,

(Еще один банальный особый случай, когда fзадается ограниченным верхним трехконтурным вентилятором. Там,fmod это также ограниченная трехконтурная схема с глубиной вентилятора, и мы знаем, как сделать PIT за детерминированное полиномиальное время.)

Ramprasad
источник