Проверка полиномиальной идентичности

В математике проверка полиномиальной идентичности (PIT) — это проблема эффективного определения того, ли два многомерных полинома идентичны . Более формально, алгоритм PIT имеет арифметическую схему , которая вычисляет полином p в поле и решает, является ли p нулевым полиномом. Определение вычислительной сложности, необходимой для проверки полиномиальной идентичности, в частности поиск детерминированных алгоритмов для PIT, является одной из наиболее важных открытых проблем сложности алгебраических вычислений.

Описание [ править ]

Вопрос «Действует ли $(x+y)(x-y)$ равный $x^{2}-y^{2}\,?$ " - это вопрос о том, идентичны ли два полинома. Как и любой вопрос о проверке идентичности полинома, его можно тривиально преобразовать в вопрос "Равен ли определенный многочлен 0?"; в этом случае мы можем спросить: "Равно ли 0?" $(x+y)(x-y)-(x^{2}-y^{2})=0$ «? Если нам дан полином как алгебраическое выражение (а не как черный ящик), мы можем подтвердить, что равенство выполняется посредством умножения и сложения методом грубой силы, но временная сложность метода грубой силы возрастает по мере того, как ${\tbinom {n+d}{d}}$ , где $n$ – количество переменных (здесь $n=2$ : $x$ является первым и $y$ это второй) и $d$ – степень многочлена (здесь $d=2$ ). Если $n$ и $d$ оба большие, ${\tbinom {n+d}{d}}$ растет в геометрической прогрессии. ^[1]

PIT касается того, идентичен ли полином нулевому полиному, а не того, всегда ли функция, реализуемая полиномом, равна нулю в данной области. Например, поле с двумя элементами GF(2) содержит только элементы 0 и 1. В GF(2) $x^{2}-x$ всегда оценивается в ноль; несмотря на это, PIT не учитывает $x^{2}-x$ быть равным нулевому многочлену. ^[2]

Определение вычислительной сложности, необходимой для проверки полиномиальной идентичности, является одной из наиболее важных открытых проблем в математической области, известной как «алгебраическая сложность вычислений». ^[1]^[3] Исследование PIT является строительным блоком для многих других областей вычислительной сложности, таких как доказательство того, что IP = PSPACE . ^[1]^[4] Кроме того, PIT имеет приложения к матрицам Тутте , а также к тестированию на простоту , где методы PIT привели к тесту на простоту AKS , первому детерминированному (хотя и непрактичному) полиномиальному алгоритму времени для тестирования на простоту. ^[1]

Формальная постановка задачи [ править ]

Учитывая арифметическую схему , которая вычисляет полином в поле , определите, равен ли полином нулевому полиному (то есть многочлену без ненулевых членов). ^[1]

Решения [ править ]

В некоторых случаях спецификация арифметической схемы не передается решателю PIT, и решатель PIT может только вводить значения в «черный ящик», реализующий схему, а затем анализировать выходные данные. Обратите внимание, что приведенные ниже решения предполагают, что любая операция (например, умножение) в данном поле занимает постоянное время; кроме того, все приведенные ниже алгоритмы черного ящика предполагают, что размер поля больше степени полинома.

Алгоритм Шварца-Циппеля обеспечивает практическое вероятностное решение, просто случайным образом проверяя входные данные и проверяя, равен ли выходной сигнал нулю. Это был первый алгоритм PIT с рандомизированным полиномиальным временем, правильность которого оказалась доказана. ^[1] Чем больше область, из которой извлекаются входные данные, тем меньше вероятность того, что Шварц-Циппель потерпит неудачу. Если случайных битов не хватает, алгоритм Чен-Као (по рациональным числам) или алгоритм Левина-Вадхана (по любому полю) требуют меньше случайных битов за счет увеличения требуемого времени выполнения. ^[2]

имеет Разреженный PIT не более $m$ ненулевые одночлены . Разреженный PIT может быть решен детерминированно за полиномиальное время от размера схемы и количества $m$ мономов, ^[1] см. также. ^[5]

PIT низкой степени имеет верхнюю границу степени полинома. Любую задачу PIT низкой степени можно свести за субэкспоненциальное время от размера схемы к задаче PIT для схем глубины четыре; поэтому PIT для схем глубины четыре (и ниже) интенсивно изучается. ^[1]

См. также [ править ]

Приложения леммы Шварца – Циппеля.

Внешние ссылки [ править ]

Конспект лекций «Проверка полиномиальной идентичности по лемме Шварца-Циппеля»
Полиномиальное тестирование идентичности, Майкл Форбс - MIT на YouTube
Лауреат премии за проверку полиномиальной идентичности

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Саксена, Нитин (22 октября 2009 г.). «Прогресс в проверке полиномиальной идентичности» . ЕССС . ISSN 1433-8092 . Проверено 17 января 2024 г.
^ Jump up to: Перейти обратно: ^а ^б Шпилька, Амир и Амир Иегудаев. «Арифметические схемы: обзор последних результатов и открытых вопросов». Основы и тенденции теоретической информатики 5.3–4 (2010): 207–388.
^ Двир, Зеев и Амир Шпилька. «Локально декодируемые коды с двумя запросами и проверкой полиномиальной идентичности для схем глубины 3». SIAM Journal on Computing 36.5 (2007): 1404-1434.
^ Ади Шамир . «IP=PSPACE». Журнал ACM (JACM) 39.4 (1992): 869-877.
^ Григорьев, Дима, Карпински, Марек и Сингер, Майкл Ф., «Быстрые параллельные алгоритмы для разреженной многомерной полиномиальной интерполяции по конечным полям», SIAM J. Comput., Том 19, № 6, стр. 1059-1063, декабрь 1990 год

[saxena-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Саксена, Нитин (22 октября 2009 г.). «Прогресс в проверке полиномиальной идентичности» . ЕССС . ISSN 1433-8092 . Проверено 17 января 2024 г.

[shpilka-2] Jump up to: Перейти обратно: ^а ^б Шпилька, Амир и Амир Иегудаев. «Арифметические схемы: обзор последних результатов и открытых вопросов». Основы и тенденции теоретической информатики 5.3–4 (2010): 207–388.

[3] Двир, Зеев и Амир Шпилька. «Локально декодируемые коды с двумя запросами и проверкой полиномиальной идентичности для схем глубины 3». SIAM Journal on Computing 36.5 (2007): 1404-1434.

[4] Ади Шамир . «IP=PSPACE». Журнал ACM (JACM) 39.4 (1992): 869-877.

[gks90-5] Григорьев, Дима, Карпински, Марек и Сингер, Майкл Ф., «Быстрые параллельные алгоритмы для разреженной многомерной полиномиальной интерполяции по конечным полям», SIAM J. Comput., Том 19, № 6, стр. 1059-1063, декабрь 1990 год

[1]

[2]

[3]

[4]

[5]

v т и Полиномы и полиномиальные функции
По степени	Нулевой полином (степень неопределена или −1 или −∞) Постоянная функция (0) Линейная функция (1) Линейное уравнение Квадратичная функция (2) Квадратное уравнение Кубическая функция (3) Кубическое уравнение Функция четвертой степени (4) Уравнение четвертой степени Квинтическая функция (5) Секстическое уравнение (6) Септическое уравнение (7)
По свойствам	Одномерный Двумерный Многомерный моном Биномиальный Трехчленный Нередуцируемый без квадратов Однородный Квазиоднородный
Инструменты и алгоритмы	Факторизация Наибольший общий делитель Разделение Метод оценки Горнера Проверка полиномиальной идентичности Результирующий Дискриминант База Грёбнер