|
|
| Строка 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>\text{P=NP} \Rightarrow \text{EXP=NEXP}</tex> | | :<tex>\text{P=NP} \Rightarrow \text{EXP=NEXP}</tex> |
Текущая версия на 19:38, 4 сентября 2022
Формулировка
- [math]\text{P=NP} \Rightarrow \text{EXP=NEXP}[/math]
Доказательство
Рассмотрим NEXP-полный язык [math]\text{BH}_{2N}=\{\langle m, x, t \rangle ~|~ m(x)=1, T(m, x) \le t \}[/math].
Докажем, что при условии выполнения равенства [math]\text{P=NP,~BH}_{2N} \in \text{EXP}[/math].
Сведем [math]\text{BH}_{2N}[/math] к [math]\text{BH}_{1N}[/math] по Карпу за экпоненциальное время [math]\left( \text{BH}_{2N} \le_{\tiny{\text{EXP}}} \text{BH}_{1N} \right)[/math].
Для этого запишем [math]\text{t}[/math] в унарной системе счисления: [math]\langle m, x, t \rangle \rightarrow \langle m, x, 1^t \rangle[/math].
Ясно, что для выполнение этого сведения потребуется выполнить [math]O(2^{p_1(t)})[/math] операций, где [math]p_1[/math] — полином.
Поскольку мы предположили, что [math]\text{P=NP}[/math], то существует детерминированная машина Тьюринга [math]M[/math], разрешающая [math]\text{BH}_{1N}[/math] за полиномиальное от длины
входа время [math]\left( T(M, \langle m, x, 1^t \rangle) ~=~ O(p_2(|\langle m, x, 1^t \rangle|)),~ p_2 \in \text{\textit{\large{poly}}} \right)[/math]. Имея ее, легко построить машину [math]M'[/math], которая сначала выполняла бы описанное выше сведение, а затем подавала бы полученный результат на вход машине [math]M[/math]. То есть [math]M'(\langle m, x, t \rangle) ~=~ M(\langle m, x, 1^t \rangle)[/math].
Заметим, что время работы машины [math]M'[/math] складывается из времени, необходимого на преобразование входа, и времени работы машины [math]M[/math].
- [math]T(M', \langle m, x, t \rangle) ~=~ O(2^{p_1(t)}) + O(p_2(|\langle m, x, 1^t \rangle|)) = O(2^{poly(|\langle m, x, t \rangle|)})[/math]
Полученное равенство означает, что [math]\text{BH}_{2N} \in \text{EXP}[/math], откуда в силу NEXP-полноты языка [math]\text{BH}_{2N}[/math] вытекает включение [math]\text{NEXP} \subset \text{EXP}[/math]. Поскольку обратное включение [math]\left(\text{NEXP} \supset \text{EXP}\right)[/math] тривиально, то это и означает, что [math]\text{EXP=NEXP}[/math]
