Коротко: метод зависит от представления многочлена. Ниже — алгоритмы для трёх стандартных случаев, доказательства корректности и оценки сложности.
1) Полином задан явно как набор одночленов (разреженное представление)
- Вход: список $m$ одночленов $c_j{x}_1^{{\alpha }_{j1}}\cdots x_n^{{\alpha }_{jn}}$.
- Алгоритм: привести к канонической форме — собрать одночлены с одинаковыми степенями (хеш/сортировка по вектору показателей), суммировать коэффициенты; проверить, что все суммарные коэффициенты равны нулю.
- Сложность: время $O(m\cdot L+m\log m)$, где $L$ — средняя стоимость обработки одного одночлена (например длина описания степеней). Память — $O(m)$. Для малых $m$ это практично. Если при суммировании коэффициенты большие по битам — учитывать сложность операций с целыми/рациональными числами.
2) Унитарный (или плотное) представление коэффициентного вектора (небольшая степень)
- Вход: коэффициенты $a_0,\dots ,a_d$ у многочлена одной переменной.
- Алгоритм: проверить, что все $a_i=0$.
- Сложность: $O(d)$ арифметических операций (с учётом битовой сложности — умножение/сложение больших чисел).
3) Полином задан как арифметическая схема/формула или «чёрный ящик» (только возможность вычислять значение)
- Решение: случайный тест (Schwartz–Zippel).
- Теорема (Schwartz–Zippel): если $f\in \mathbb{F}[x_1,\dots ,x_n]$ — ненулевой полином с полной степенью $\mathrm{deg}f=d$, и точки выбираются равномерно из множества $S\subset \mathbb{F}$, то
$$\underset{a\in S^n}{\mathrm{Pr}}[f(a)=0]\le \frac{d}{|S|}.$$ - Алгоритм (рандомизированный, «польовый»):
1. Пусть известна верхняя оценка степени $d$. Выберите множество $S$ размера $|S|=s$ (часто берут случайные элементы из конечного поля ${\mathbb{F}}_p$).
2. Повторить $t$ раз: выбрать случайный $a\in S^n$, вычислить $f(a)$. Если для какого‑то $a$ $f(a)\ne 0$, вывести «не тождественно ноль».
3. Если все $t$ испытаний дали $0$, вывести «скорее всего тождественно ноль».
- Гарантии и параметры: вероятность ошибки (выдать «нулевой», когда полином ненулевой) не превосходит $(d/s{)}^t$. Часто берут $s=2d$ и $t=\lceil {\log }_2(1/\delta )\rceil$ для требуемой вероятности ошибки $\delta$.
- Сложность: если одна оценка $f(a)$ стоит $E$ (время вычисления схемы), то общее время $O(t\cdot E)$. Для получения малыми затратами экспоненциальной гарантии достаточно $t=O(\log (1/\delta ))$.
Дополнительные замечания и практические детали
- Если коэффициенты целые/рациональные и вычисления ведутся с учётом битов, часто удобней выбирать случайное $a$ в поле ${\mathbb{F}}_p$ с большим простым $p$ (модульная арифметика) — так избегают переполнения и контролируют вероятность совпадений по модулю. Выбор $p$ должен быть таким, чтобы вероятность «случайного зануления» по модулю мала (например $p$ значительно больше верхней границы абсолютных значений коэффициентов).
- Детерминированные алгоритмы существуют для специальных случаев: унитарный полином (интерполяция), разрежённые полиномы с малым числом одночленов (спарс‑интерполяция), для некоторых типов схем (read‑once) — в полиномиальное время. В общем случае (полином задан схемой) детерминированный полиномиальный алгоритм для PIT неизвестен (открытая проблема в теории сложности — дерндоминизация PIT).
- Если можно развернуть выражение в явный список одночленов («экспансия» формулы), то проверка сводится к случаю 1, но развёртка может быть экспоненциальной по размеру схемы.
Краткий вывод: если полином явно дан списком одночленов или вектором коэффициентов — собрать одночлены/проверить коэффициенты (детерминированно, время линейно по входу). Если полином задан как схема/чёрный ящик — наиболее практичный и быстрый общий метод — случайный тест по Schwartz–Zippel: время $O(t\cdot E)$, ошибка ≤ $(d/|S|{)}^t$.