Изменения

Заметим что исходная задача звучала как проверка двух полиномов не равенство. Мы свели ее к проверке полинома на равенство нулю путем такого преобразования. Пусть у нас было две арифметические схемы <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> может оказаться довольно затратной по времени. Однако существует эффективный рандомизированный алгоритм основанный на лемме Шварца-Зиппеля, которую здесь мы оставим без доказательства.