|
|
| Строка 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 Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | ==Определение классов RP и coRP== | | ==Определение классов RP и coRP== |
| | Классы языков '''RP''' и '''coRP''' определяются следующим образом: | | Классы языков '''RP''' и '''coRP''' определяются следующим образом: |
Определение классов RP и coRP
Классы языков RP и coRP определяются следующим образом:
[math]\mbox{RP} = \{L \mid \exists m: \mbox{P}(m(x) = 1 \mid x \in L)\geq \frac{1}{2},~ \mbox{P}(m(x) = 0 \mid x \notin L) = 1\}[/math]
[math]\mbox{coRP} = \{L \mid \exists m: \mbox{P}(m(x) = 0 \mid x \notin L)\geq \frac{1}{2},~ \mbox{P}(m(x) = 1 \mid x \in L) = 1\}[/math]
В этих определениях [math]m[/math] - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.
Теорема о равенстве ZPP и пересечения RP и coRP
[math]\mbox{ZPP} = \mbox{RP}\bigcap\mbox{coRP}[/math]
Воспользуемся следующим определением ZPP :
[math]\mbox{ZPP} = \{ L \mid \exists m : L(m)=L,~ p(m(x) = ?) \le \frac{1}{2} \}[/math],
где [math]m[/math] - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.
Доказательство
[math]\mbox{ZPP} \subset\mbox{RP}[/math]
Пусть язык [math] L = L(m_1) \in \mbox{ZPP}[/math]. Нужно показать, что [math]\L \in \mbox{RP}[/math].
Алгоритм для вероятностной машины Тьюринга [math]m[/math] из определения класса RP будет выглядеть так:
[math]m[/math](x){
switch ([math]m_1[/math](x))
{
case 0: return 0;
case 1: return 1;
case ?: return 0; //[math]m_1[/math] выдала ответ "не знаю"
}
}
Так как машина [math]m_1[/math] выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах [math]0[/math] или [math]1[/math] никогда не ошибается, вероятность правильного ответа [math]m[/math] в случае, если слово принадлежит языку, будет не меньше одной второй, а слово не из языка всегда будет обнаружено, что соответствует определению класса RP.
Аналогичным образом доказывается, что [math]\L \in \mbox{coRP}[/math]:
[math]m[/math](x){
switch ([math]m_1[/math](x))
{
case 0: return 0;
case 1: return 1;
case ?: return 1; //[math]m_1[/math] выдала ответ "не знаю"
}
}
Осталось показать, что [math] \mbox{RP} \bigcap \mbox{coRP} \subset \mbox{ZPP} [/math]. То есть если [math]L \in \mbox{RP} [/math] и [math]L \in \mbox{coRP} [/math], то [math]L \in \mbox{ZPP} [/math].
Пусть [math]m_1[/math] - вероятностная машина Тьюринга для языка [math]L[/math] из определения RP, а [math]m_2[/math] - соответствующая машина из определения coRP. Тогда алгоритм для машины [math]m[/math] из определения ZPP будет устроен следующим образом:
[math]m[/math](x){
if ([math]m_1[/math](x))
return 1;
if (![math]m_2[/math](x))
return 0;
return ?; //возвращаем ответ "не знаю"
}
Пусть [math] x \in L [/math]. Тогда вероятность [math]\mbox{P}(m_1(x) = 1) \geq \frac{1}{2}[/math]. Если же [math]m_1[/math] вернула [math]0[/math], то, поскольку всегда [math]m_2(x) = 1[/math] в этой ситуации, машина [math]m[/math] вернет "не знаю". Получается, что [math]\mbox{P}(m(x) = ?) \leq \frac{1}{2}[/math].
Аналогично, если [math] x \notin L [/math], то [math]\mbox{P}(m(x) = 0) = \mbox{P}(m_2(x) = 0) \geq \frac{1}{2}[/math].
В итоге получаем, что машина [math]m[/math] никогда не ошибается и возвращает определенный результат с вероятностью большей либо равной одной второй, что соответствует определению класса ZPP.
