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

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

Описание

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

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

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

Формальная постановка проблемы

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

Решения

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

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

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

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

Смотрите также

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

внешняя ссылка

• Конспект лекций на тему "Проверка полиномиальной идентичности по лемме Шварца-Циппеля"
• Тестирование полиномиальной идентичности Майкла Форбса - Массачусетский технологический институт на YouTube
• Лауреат премии за тестирование полиномиальной идентичности

Рекомендации

1. Саксена, Нитин. «Прогресс в тестировании полиномиальной идентичности». Бюллетень EATCS 99 (2009): 49-79.
2. Шпилка, Амир и Амир Иегудаофф. «Арифметические схемы: обзор последних результатов и открытых вопросов». Основы и тенденции теоретической информатики 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.
5. Григорьев, Дима, Карпинский, Марек, и Зингер, Майкл Ф., "Быстрые параллельные алгоритмы для разреженной многомерной полиномиальной интерполяции над конечными полями", SIAM J. Comput., Том 19, № 6, стр. 1059-1063, декабрь 1990 г.