Проверка полиномиальной идентичности - 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
Лауреат премии за тестирование полиномиальной идентичности