45
правок
Изменения
Нет описания правки
<tex> p(q = 0) \le \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} </tex>, что и требовалось доказать.
== Применение ==
С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу <tex> coRP </tex>.
=== Формулировка задачи ===
Пусть даны два полинома <tex> - p </tex> и <tex> q </tex>, Нужно проверить, верно ли, что <tex> p \equiv q </tex>.
=== Утверждение ===
Сформулированная выше задача принадлежит классу <tex> coRP </tex>.
