63
правки
Изменения
→Алгоритм
Заметим что исходная задача звучала как проверка двух полиномов не равенство. Мы свели ее к проверке полинома на равенство нулю путем такого преобразования. Пусть у нас было две арифметические схемы <tex>C, C'</tex> которые нужно проверить на равенство. Мы строим новую схему <tex>D : D(x_1, ..., x_n) = C(x_1, ..., x_n) - C'(x_1, ..., x_n)</tex>.
====Алгоритм====
Так как раскрытие всех скобок в полиноме может привести к экспоненциальному количеству мономов. То проверка на принадлежность классу <tex>ZEROP</tex> может оказаться довольно затратной по времени. Однако существует эффективный рандомизированный алгоритм основанный на лемме Шварца-Зиппеля, которую здесь мы оставим без доказательства.
{{Лемма
|statement= Пусть <tex>p(x_1, x_2, ..., x_m)</tex> полином с общей степенью не более <tex>d</tex>. <tex>S</tex> {{---}} конечный набор чисел. Тогда если <tex>a_1, a_2, ..., a_m</tex> случайно выбранные числа из <tex>S</tex> то:
<tex>Pr[p(a_1, a_2, ..., a_m) \ne 0] \ge 1 - \frac{d}{|S|}</tex>. Где <tex>Pr[x]</tex> {{---}} вероятность события <tex>x</tex>
}}
Нетрудно видеть что у схемы <tex>C</tex> размера <tex>m</tex> с <tex>n</tex> переменными общая степень не больше <tex>2^m</tex>. Получаем следующий алгоритм: выбираем <tex>n</tex> чисел из набора <tex>[1 .. 10 \cdot 2^m]</tex>. Вычисляем схему на этих числах. Если получился ноль то говорим что <tex>C \in ZEROP</tex>. Иначе говорим что <tex>C \notin ZEROP</tex>.
Если <tex>C \in ZEROP</tex>, то алгорим всегда выдаст правильный ответ. Если <tex>C \notin ZEROP</tex> то алгоритм выдаст правильный ответ с вероятностью <tex>\ge frac{9}{10}</tex>. Однако есть проблема. Числа которые получаются в результате вычисленний могут быть порядка <tex>(10 \cdot 2^m)^{2^m}</tex>. Такие числа требуют экспоненциальное число бит только для представления не говоря уже про операции над ними.
Мы решим эту проблему с помощью вычислений по модулю <tex>k</tex>, где <tex>k</tex> - слуйчайное число <tex>\le 2^{2^m}</tex>. Таким образом вместо вычисления <tex>y = C(x_1, x_2, ..., x_m)</tex>, мы считаем значение <tex>y (mod k)</tex>. Очевидно что если <tex>y = 0<tex>, то <tex>y mod k = 0</tex>. Утверждается что если <tex>y \ne 0</tex>, то с вероятностью хотябы <tex>\\delta = frac{1}{10m}</tex>, <tex>k</tex> не делится на <tex>y</tex>. Действительно, пусть <tex>y \ne 0</tex>
