|
|
| Строка 1: |
Строка 1: |
| − | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
| |
| − | |+
| |
| − | |-align="center"
| |
| − | |'''НЕТ ВОЙНЕ'''
| |
| − | |-style="font-size: 16px;"
| |
| − | |
| |
| − | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
| |
| − |
| |
| − | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
| |
| − |
| |
| − | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
| |
| − |
| |
| − | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
| |
| − |
| |
| − | ''Антивоенный комитет России''
| |
| − | |-style="font-size: 16px;"
| |
| − | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
| |
| − | |-style="font-size: 16px;"
| |
| − | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | == Формулировка == | | == Формулировка == |
| | Пусть задан полином <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> S </tex>. Тогда <tex> P(q(r_1, ..., r_n) = 0) \leqslant \frac{d}{|S|} </tex>. | | Пусть задан полином <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> S </tex>. Тогда <tex> P(q(r_1, ..., r_n) = 0) \leqslant \frac{d}{|S|} </tex>. |
Формулировка
Пусть задан полином [math] q(x_1, ..., x_n) \not\equiv 0 [/math] степени [math] d [/math] над полем [math] F [/math], а также произвольное множество [math] S \subset F: |S| \lt \infty [/math]. Пусть также [math] \{r_i\}_{i=1}^n [/math] — набор независимых случайных величин, равномерно распределенных в [math] S [/math]. Тогда [math] P(q(r_1, ..., r_n) = 0) \leqslant \frac{d}{|S|} [/math].
Доказательство
Проведем доказательство леммы индукцией по [math] n [/math].
База индукции
В случае, когда [math] n = 1 [/math], утвержение следует из того, что произвольный полином степени [math] d [/math] над полем имеет не более чем [math] d [/math] корней.
Индукционный переход
Пусть утверждение верно для всех полиномов от не более чем [math] n - 1 [/math] переменных. Разложим [math] q [/math] по степеням [math] x_n [/math]:
[math] q(x_1, ..., x_n) = \sum_{i=0}^d q_i(x_1, ..., x_{n-1}) x_n^i [/math]
Так как [math] q \not\equiv 0 [/math], хотя бы один полином [math] q_i \not\equiv 0 [/math]. Пусть [math] j = \max \{ i \mid q_i \not\equiv 0\} [/math].
По формуле полной вероятности имеем:
[math] 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) [/math].
Заметим, что [math] q_j [/math] — полином от [math] n - 1 [/math] переменных, а потому к нему применимо предположение индукции. Кроме того, [math] \mathrm{deg} \, q_j \le d - j [/math]. Таким образом, [math] P(q = 0 \mid q_j = 0) P(q_j = 0) \leqslant 1 \cdot \frac{d - j}{|S|} [/math].
Для получения оценки второго слагаемого зафиксируем некоторый набор [math] \{x_1, ..., x_{n-1}\} [/math], для которого [math] q_j(x_1, ..., x_{n-1}) \ne 0 [/math].
Тогда для [math] q(x_1, ..., x_n) [/math] как для полинома одной переменной степени [math] j [/math] будет выполнено:
[math] P(q = 0 \mid q_j \ne 0) P(q_j \ne 0) \leqslant \frac{j}{|S|} \cdot 1 [/math].
[math] P(q = 0) \leqslant \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} [/math], что и требовалось доказать.
Применение
С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу coRP.
Формулировка задачи
Пусть даны два полинома — [math] p(x_1, ..., x_n) [/math] и [math] q(x_1, ..., x_n) [/math]. Необходимо проверить, верно ли, что [math] p \equiv q [/math].
Утверждение
Сформулированная выше задача принадлежит классу [math] \mathrm{coRP} [/math].
Доказательство
Для доказательства построим такой алгоритм m, что:
- [math] P(m(\langle p, q \rangle) = 1 \mid p \equiv q) = 1 [/math]
- [math] P(m(\langle p, q \rangle) = 0 \mid p \not\equiv q) \geqslant \frac{1}{2} [/math]
Для этого рассмотрим полином [math] h = p - q [/math]. Очевидно, что [math] h \equiv 0 \Leftrightarrow p \equiv q [/math]. Рассмотрим [math] h [/math] над некоторым полем [math] F [/math]. Очевидно, что если [math] h \equiv 0 [/math], то это будет выполнено и в [math] F [/math] (обратное, вообще говоря, неверно). Возьмем случайный набор [math] \{x_1, ..., x_n\} [/math]. По
доказанной выше лемме [math] p(h(x_1, ..., x_n) = 0) \leqslant \frac {\mathrm{deg} \, h}{|F|} [/math]. Тогда алгоритм, по данным [math] p [/math] и [math] q [/math] выдающий [math] [h(x_1, ..., x_n) = 0] [/math], удовлетворяет поставленным условиям, лишь только [math] |F| \geqslant 2 \mathrm{deg} \, h [/math], что тем более верно, если [math] |F| \geqslant 2 \max(\mathrm{deg} \, p, \mathrm{deg} \, q) [/math].
