В математике проверка идентичности полиномов (PIT) - это проблема эффективного определения идентичности двух многомерных полиномов . Более формально, алгоритм PIT представляет собой арифметическую схему, которая вычисляет многочлен p в поле и решает, является ли p нулевым многочленом. Определение вычислительной сложности, необходимой для проверки полиномиальной идентичности, является одной из наиболее важных открытых проблем алгебраической вычислительной сложности.
Описание
На вопрос "Есть ли равный "- это вопрос о том, идентичны ли два многочлена. Как и любой вопрос о проверке идентичности многочлена, его можно тривиально преобразовать в вопрос" Равен ли некоторый многочлен 0? "; в этом случае мы можем спросить" Имеет ли "? Если нам дан многочлен в виде алгебраического выражения (а не в виде черного ящика), мы сможем подтвердить, что равенство выполняется путем перемножения и сложения грубой силы, но временная сложность подхода грубой силы растет по мере того, как, где - количество переменных (здесь : это первый и второй), и - степень полинома (здесь). Если а также оба большие, растет в геометрической прогрессии. [1]
PIT касается того, идентичен ли многочлен нулевому многочлену, а не то, всегда ли функция, реализованная многочленом, оценивается как ноль в данной области. Например, поле с двумя элементами GF (2) содержит только элементы 0 и 1. В GF (2)всегда равен нулю; несмотря на это, НДФЛ не учитываетбыть равным нулевому многочлену. [2]
Определение вычислительной сложности, необходимой для проверки полиномиального тождества, является одной из наиболее важных открытых проблем в математическом подполе, известном как «сложность алгебраических вычислений». [1] [3] Изучение PIT является строительным блоком для многих других областей вычислительной сложности, таких как доказательство того, что IP = PSPACE . [1] [4] Кроме того, PIT имеет приложения к матрицам Тутте, а также к проверке простоты , где методы PIT привели к тесту на простоту AKS , первому детерминированному (хотя и непрактичному) полиномиальному алгоритму времени для проверки простоты. [1]
Формальная постановка проблемы
Для данной арифметической схемы, которая вычисляет многочлен в поле , определите, равен ли многочлен нулевому многочлену (то есть многочлену без ненулевых членов). [1]
Решения
В некоторых случаях спецификация арифметической схемы не передается решателю PIT, и решатель PIT может только вводить значения в «черный ящик», который реализует схему, а затем анализировать вывод. Обратите внимание, что в приведенных ниже решениях предполагается, что любая операция (например, умножение) в данном поле занимает постоянное время; кроме того, все приведенные ниже алгоритмы черного ящика предполагают, что размер поля больше, чем степень полинома.
Шварц-Zippel алгоритм обеспечивает практическое решение вероятностный, просто случайным тестирование входов и проверки , является ли выходной сигнал равен нулю. Это был первый рандомизированный алгоритм PIT с полиномиальным временем, корректность которого была подтверждена. [1] Чем шире область, из которой взяты исходные данные, тем менее вероятно, что Шварц – Циппель потерпит неудачу. Если случайных битов не хватает, алгоритм Чен-Као (над рациональными числами) или алгоритм Левина-Вадхана (над любым полем) требует меньше случайных битов за счет большего требуемого времени выполнения. [2]
Разреженный PIT имеет не болеененулевые мономиальные члены. Разреженный PIT может быть решен детерминированно за полиномиальное время от размера схемы и количествамономов, см. также [1] . [5]
Низкая PIT степени имеет верхнюю границу на степени полинома. Любая проблема PIT низкой степени может быть уменьшена за субэкспоненциальное время размера схемы до проблемы PIT для схем с глубиной четыре; поэтому PIT для схем с глубиной четыре (и ниже) интенсивно изучается. [1]
Смотрите также
Внешние ссылки
- Конспект лекций на тему «Проверка полиномиальной идентичности по лемме Шварца-Циппеля»
- Тестирование полиномиальной идентичности Майкла Форбса - Массачусетский технологический институт на YouTube
- Лауреат премии за тестирование полиномиальной идентичности
Рекомендации
- ^ a b c d e f g h Саксена, Нитин. «Прогресс в тестировании полиномиальной идентичности». Бюллетень EATCS 99 (2009): 49-79.
- ^ a b Шпилка, Амир и Амир Иегудаофф. «Арифметические схемы: обзор последних результатов и открытых вопросов». Основы и тенденции теоретической информатики 5.3–4 (2010): 207-388.
- ^ Dvir, Зив, и Амир Шпилька. «Локально декодируемые коды с двумя запросами и проверкой полиномиальной идентичности для схем глубины 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 г.