|
|
| Строка 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 Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | {{Определение | | {{Определение |
| | |definition=<tex> \mathrm{BH_{1N}} </tex> (от ''bounded halting unary non-deterministic'') <tex>= \lbrace \langle m, x, 1^t \rangle \mid m </tex> {{---}} [[Недетерминированные вычисления|недетерминированная машина Тьюринга]], <tex> m(x) = 1, T(m,x) \leqslant t \rbrace </tex>. | | |definition=<tex> \mathrm{BH_{1N}} </tex> (от ''bounded halting unary non-deterministic'') <tex>= \lbrace \langle m, x, 1^t \rangle \mid m </tex> {{---}} [[Недетерминированные вычисления|недетерминированная машина Тьюринга]], <tex> m(x) = 1, T(m,x) \leqslant t \rbrace </tex>. |
| Определение: |
| [math] \mathrm{BH_{1N}} [/math] (от bounded halting unary non-deterministic) [math]= \lbrace \langle m, x, 1^t \rangle \mid m [/math] — недетерминированная машина Тьюринга, [math] m(x) = 1, T(m,x) \leqslant t \rbrace [/math]. |
То есть [math] \mathrm{BH_{1N}} [/math] — язык троек [math] \langle m, x, 1^t \rangle [/math] таких, что недетерминированная машина Тьюринга [math] m [/math] на входной строке [math] x [/math] возращает [math]1[/math] за время [math] T(m, x) \leqslant t [/math] и [math] 1^{t} [/math] — запись [math] t [/math] в унарной системе счисления.
| Теорема: |
[math] \mathrm{BH_{1N}} \in \mathrm{NPC} [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
- [math] \mathrm{BH_{1N}} \in \mathrm{NP} [/math]
- Можно написать недетерминированную программу, которая будет по [math] \langle m, x, 1^t \rangle [/math] моделировать [math] t [/math] шагов [math] m [/math] на входе [math] x [/math], выбирая недетерминированно соответствующие недетерминированные переходы, и если машина за это время допустила слово, то только тогда [math] \langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} [/math].
- [math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math]
- Нужно доказать, что [math] \forall L \in \mathrm{NP} [/math] существует полиномиальное сведение по Карпу к языку [math] \mathrm{BH_{1N}} [/math]. Рассмотрим произвольный язык [math] L \in \mathrm{NP} [/math]. Для него существует недетерминированная машина Тьюринга [math] m [/math] и полином [math] p(x) [/math], такие что [math] T(m, x) \leqslant p(|x|)[/math] и [math] L(m) = L [/math]. Докажем, что [math] \exists f \in \widetilde{\mathrm{P}} : L \leqslant_f \mathrm{BH_{1N}} [/math]. Рассмотрим функцию [math] f(x) = \langle m, x, 1^{p(|x|)} \rangle [/math], по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени [math] p(|x|)[/math] в унарной системе счисления.
- Проверим, что [math] x \in L \Leftrightarrow f(x) \in \mathrm{BH_{1N}} [/math].
- Пусть [math] x \in L [/math]. Тогда [math] m(x) = 1 [/math] за время не более [math] p(|x|) [/math], а значит [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \in \mathrm{BH_{1N}} [/math].
- Пусть [math]x \notin L[/math]. Тогда [math]m(x) = 0[/math] и [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} [/math].
- Это значит, что [math] \forall L \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : L \leqslant_f \mathrm{BH_{1N}} [/math], и из этого следует, что [math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math].
|
| [math]\triangleleft[/math] |
См. также
