|
|
Строка 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>RP, RP_1, RP_2</tex>== | | ==Определение классов <tex>RP, RP_1, RP_2</tex>== |
| Множество языков [[Сложностные_классы_RP_и_coRP |'''RP''']] определяется следующим образом: | | Множество языков [[Сложностные_классы_RP_и_coRP |'''RP''']] определяется следующим образом: |
Текущая версия на 19:25, 4 сентября 2022
Определение классов [math]RP, RP_1, RP_2[/math]
Множество языков RP определяется следующим образом:
[math]RP = \{L \mid \exists m: P(m(x) = 1 \mid x \in L) \geq \frac{1}{2}, P(m(x) = 0 \mid x \notin L) = 1\}[/math]
Определим множества языков [math]RP_1[/math] и [math]RP_2[/math]:
[math]RP_1 = \{L \mid \exists m: P(m(x) = 1 \mid x \in L) \geq \frac{1}{p(|x|)}, P(m(x) = 0 \mid x \notin L) = 1\}[/math]
[math]RP_2 = \{L \mid \exists m: P(m(x) = 1 \mid x \in L) \geq 1 - \frac{1}{2^{p(|x|)}}, P(m(x) = 0 \mid x \notin L) = 1\}[/math]
В приведенных определениях [math]p(|x|)[/math] — некий полином, а [math]m[/math] — вероятностная машина Тьюринга, время работы которой в худшем случае составляет полином от длины входа.
В классе [math]RP_1[/math] ослаблено ограничение на вероятность ошибки ответа, а в классе [math]RP_2[/math] усилено. Соответственно [math]RP_1[/math] называется слабым определением класса [math]RP[/math], а [math]RP_2[/math] — сильным.
Доказательство эквивалентности определений
Включение [math]RP_2 \subset RP \subset RP_1[/math] очевидно, следовательно осталось доказать обратное включение [math]RP_1 \subset RP \subset RP_2[/math]. Доказательство данного утверждения проводится с помощью метода уменьшения ошибки в классе [math]RP[/math].
- Докажем включение [math]RP_1 \subset RP[/math]
Выясним, сколько раз требуется запустить машину Тьюринга [math]m[/math] из [math]RP_1[/math], для того, чтобы вероятность ошибки была меньше [math]\frac{1}{2}[/math]. Запустим машину [math]m[/math] [math]k[/math] раз, тогда вероятность ошибки составит [math](1 - \frac{1}{p(n)})^k[/math]. Получим неравенство: [math](1 - \frac{1}{p(n)})^k \lt \frac{1}{2}[/math]
Логарифмируя, сведем к следующему: [math]k\ ln(1 - \frac{1}{p(n)}) \lt ln(\frac{1}{2})[/math]
Разложив логарифм в левой части в ряд, получим: [math]k(-\frac{1}{p(n)} + o(\frac{1}{p(n)})) \lt ln(\frac{1}{2})[/math]
Откуда [math]k \gt p(n)ln(2)[/math], где [math]n[/math] — длина входа. То есть при [math]k[/math], удовлетворяющем полученному неравенству, вероятность ошибки не будет превышать [math]\frac{1}{2}[/math], а значит [math]RP_1 \subset RP[/math].
- Докажем включение [math]RP \subset RP_2[/math]
Доказательство проводится аналогично приведенному в первой части. Запустим машину [math]m[/math] из [math]RP[/math] [math]k[/math] раз. С учетом ограничения, введенного в определении класса [math]RP_2[/math], получим неравенство: [math](\frac{1}{2})^k \lt \frac{1}{2^{p(n)}}[/math].
Прологарифмировав и сократив обе части неравенства на [math]ln(\frac{1}{2})[/math], получим неравенство: [math]k \gt p(n)[/math]. То есть машина [math]m[/math], запущенная [math]k[/math] раз, выдает неверный ответ с вероятностью, удовлетворяющей определению класса [math]RP_2[/math], а значит [math]RP \subset RP_2[/math].
Эквивалентность определений класса [math]RP[/math] доказана.