Изменения

Пусть задан полином <tex> q(x_1, ..., x_n) \not\equiv 0 </tex> степени <tex> d </tex> над полем <tex> F </tex>, а также произвольное множество <tex> S \subset F: |S| < \infty </tex>. Пусть также <tex> \{r_i\}_{i=1}^n </tex> - — набор независимых случайных величин, равномерно распределенных в <tex> F S </tex>. Тогда <tex> pP(q(r_1, ..., r_n) = 0) \le leqslant \frac{d}{|S|} </tex>.

Проведем доказательство теоремы леммы индукцией по <tex> n </tex>.

Пусть утверждение верно для всех полиномов степени от не более чем <tex> n - 1 </tex> (и для всех меньших)переменных. Разложим <tex> q </tex> по степеням <tex> x_n </tex>:

Так как <tex> q \not\equiv 0 </tex>, хотя бы один полином <tex> q_i \not\equiv 0 </tex>. Пусть <tex> j = \max \{ i \mid q_i \not\equiv 0\} </tex>.По формуле полной вероятности имеем:<tex> P(q = 0) = P(q = 0 \mid q_j = 0) P(q_j = 0) + P(q = 0 \mid q_j \ne 0) P(q_j \ne 0) </tex>. Заметим, что <tex> q_j </tex> — полином от <tex> n - 1 </tex> переменных, а потому к нему применимо предположение индукции. Кроме того, <tex> \mathrm{deg} \, q_j \le d - j </tex>. Таким образом, <tex> P(q = 0 \mid q_j = 0) P(q_j = 0) \leqslant 1 \cdot \frac{d - j}{|S|} </tex>. Для получения оценки второго слагаемого зафиксируем некоторый набор <tex> \{x_1, ..., x_{n-1}\} </tex>, для которого <tex> q_j(x_1, ..., x_{n-1}) \ne 0 </tex>.Тогда для <tex> q(x_1, ..., x_n) </tex> как для полинома одной переменной степени <tex> j </tex> будет выполнено:<tex> P(q = 0 \mid q_j \ne 0) P(q_j \ne 0) \leqslant \frac{j}{| q_i S|} \cdot 1 </tex>. <tex> P(q = 0) \leqslant \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} </tex>, что и требовалось доказать. == Применение ==С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу [[Сложностные классы RP и coRP|coRP]].=== Формулировка задачи ===Пусть даны два полинома — <tex> p(x_1, ..., x_n) </tex> и <tex> q(x_1, ..., x_n) </tex>. Необходимо проверить, верно ли, что <tex> p \equiv q </tex>. === Утверждение ===Сформулированная выше задача принадлежит классу <tex> \mathrm{coRP} </tex>. === Доказательство ===Для доказательства построим такой алгоритм m, что:* <tex> P(m(\langle p, q \rangle) = 1 \mid p \equiv q) = 1 </tex>* <tex> P(m(\langle p, q \rangle) = 0 \mid p \not\equiv q) \geqslant \frac{1}{2} </tex> Для этого рассмотрим полином <tex> h = p - q </tex>. Очевидно, что <tex> h \equiv 0 \Leftrightarrow p \equiv q </tex>. Рассмотрим <tex> h </tex> над некоторым полем <tex> F </tex>. Очевидно, что если <tex> h \equiv 0</tex>, то это будет выполнено и в <tex> F </tex> (обратное, вообще говоря, неверно). Возьмем случайный набор <tex> \{x_1, ..., x_n\} </tex>. Подоказанной выше лемме <tex> p(h(x_1, ..., x_n) = 0) \leqslant \frac {\mathrm{deg} \, h}{|F|} </tex>. Тогда алгоритм, по данным <tex> p </tex> и <tex> q </tex> выдающий <tex> [h(x_1, ..., x_n) = 0] </tex>, удовлетворяет поставленным условиям, лишь только <tex> |F| \geqslant 2 \mathrm{deg} \, h </tex>, что тем более верно, если <tex> |F| \geqslant 2 \max(\mathrm{deg} \, p, \mathrm{deg} \, q) </tex>.