Теорема Левина - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:06:41Z

rollbackEdits.php mass rollback

194.88.143.66 в 06:19, 1 сентября 2022

2022-09-01T06:19:10Z

Kirelagin в 10:07, 5 июня 2012

2012-06-05T10:07:24Z

Kirelagin в 10:05, 5 июня 2012

2012-06-05T10:05:15Z

Kirelagin в 09:46, 5 июня 2012

2012-06-05T09:46:21Z

194.85.161.2 в 13:45, 4 июня 2012

2012-06-04T13:45:15Z

Kirelagin в 18:37, 31 мая 2012

2012-05-31T18:37:52Z

Kirelagin в 18:22, 31 мая 2012

2012-05-31T18:22:55Z

Kirelagin: Байдаров всё внимательно читает и следит за тобой!

2012-05-31T18:20:52Z

Байдаров всё внимательно читает и следит за тобой!

Kirelagin в 18:08, 31 мая 2012

2012-05-31T18:08:27Z

← Предыдущая		Версия 16:06, 4 сентября 2022
Строка 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 Майкл Наки].
−	\|}
−
	{{Теорема		{{Теорема
	\|author=Левин		\|author=Левин

← Предыдущая		Версия 06:19, 1 сентября 2022
Строка 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 Майкл Наки].
		+	\|}
		+
	{{Теорема		{{Теорема
	\|author=Левин		\|author=Левин

@@ Строка 10: / Строка 10: @@
 Пронумеруем все программы <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Подадим им на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-1}</tex> и не делится на <tex>2^{k}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге начиная с <tex>2^{k-1}</tex>-го. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>2^{k-1} + (T(P_k, x) - 1) \cdot 2^k</tex> шагов.
-Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, будем на соответствующих шагах запускать проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу ничего не делая на тех шагах, когда должна была исполняться <tex>p_k</tex>.
+Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, будем на соответствующих шагах запускать проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу, ничего не делая на тех шагах, когда должна была исполняться <tex>p_k</tex>.
 Таким образом, если некоторая программа <tex>q = p_m</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>2^{m-1} + (T(p_m,x) + T(R, \langle x,p_m(x) \rangle) - 1) \cdot 2^m</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>2^{m-1} + (T(p_m,x) + poly(|x|)) \cdot 2^m = 2^m \cdot T(q,x) + poly(|x|)</tex>.

@@ Строка 8: / Строка 8: @@
 Построим «оптимальную» программу <tex>p(x)</tex>.
-Пронумеруем все программы <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Поместим их в различные потоки, подадим на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-1}</tex> и не делится на <tex>2^{k}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге начиная с <tex>2^{k-1}</tex>-го. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>2^{k-1} + (T(P_k, x) - 1) \cdot 2^k</tex> шагов.
+Пронумеруем все программы <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Подадим им на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-1}</tex> и не делится на <tex>2^{k}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге начиная с <tex>2^{k-1}</tex>-го. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>2^{k-1} + (T(P_k, x) - 1) \cdot 2^k</tex> шагов.
-Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, запустим в том же потоке проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу больше ничего не запуская в этом потоке.
+Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, будем на соответствующих шагах запускать проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу ничего не делая на тех шагах, когда должна была исполняться <tex>p_k</tex>.
 Таким образом, если некоторая программа <tex>q = p_m</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>2^{m-1} + (T(p_m,x) + T(R, \langle x,p_m(x) \rangle) - 1) \cdot 2^m</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>2^{m-1} + (T(p_m,x) + poly(|x|)) \cdot 2^m = 2^m \cdot T(q,x) + poly(|x|)</tex>.

@@ Строка 4: / Строка 4: @@
 Для любого языка <tex>L \in \Sigma_1</tex> и соответствующего ему (из определения <tex>\Sigma_1</tex>) отношения <tex>R</tex> существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа <tex>p</tex>, сопоставляющая словам из <tex>L</tex> их сертификаты, то есть:
 # <tex>x \in L \Leftrightarrow R(x, p(x)) = 1</tex>;
-# для любой другой программы <tex>q</tex>, для которой верно <tex>x \in L \Leftrightarrow R(x, q(x)) = 1</tex>, найдутся такие константа <tex>c</tex> и полином <tex>r</tex>, что <tex>\forall x \Rightarrow T(p, x) \le c \cdot T(q, x) + r(|x|)</tex>.
+# для любой другой программы <tex>q</tex>, для которой верно <tex>x \in L \Leftrightarrow R(x, q(x)) = 1</tex>, найдутся такие константа <tex>c</tex> и полином <tex>r</tex>, что для любого <tex>x</tex> выполняется: <tex>T(p, x) \le c \cdot T(q, x) + r(|x|)</tex>.
 |proof=
 Построим «оптимальную» программу <tex>p(x)</tex>.

@@ Строка 17: / Строка 17: @@
 == См. также ==
 *[[Класс P]]
-*[[Недетерминированные вычисления. Классы NP и Σ₁]]
+*[[Классы_NP_и_Σ₁]]
 [[Категория: Теория сложности]]

@@ Строка 8: / Строка 8: @@
 Построим «оптимальную» программу <tex>p(x)</tex>.
-Пронумеруем все программы <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Поместим их в различные потоки, подадим на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-1}</tex> и не делится на <tex>2^{k}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге начиная с <tex>k</tex>-того. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>k + (T(P_k, x) - 1) \cdot 2^k</tex> шагов.
+Пронумеруем все программы <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Поместим их в различные потоки, подадим на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-1}</tex> и не делится на <tex>2^{k}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге начиная с <tex>k</tex>-того. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>2^{k-1} + (T(P_k, x) - 1) \cdot 2^k</tex> шагов.
 Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, запустим в том же потоке проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу больше ничего не запуская в этом потоке.
-Таким образом, если некоторая программа <tex>p_k</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>k + (T(p_k,x) + T(R, \langle x,p_k(x) \rangle) - 1) \cdot 2^k</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>k + (T(p_k,x) + poly(|x|)) \cdot 2^k = 2^k \cdot T(p_k,x) + poly(|x|)</tex>.
+Таким образом, если некоторая программа <tex>p_k</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>2^{k-1} + (T(p_k,x) + T(R, \langle x,p_k(x) \rangle) - 1) \cdot 2^k</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>2^{k-1} + (T(p_k,x) + poly(|x|)) \cdot 2^k = 2^k \cdot T(p_k,x) + poly(|x|)</tex>.
 }}