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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:27:17Z

rollbackEdits.php mass rollback

91.212.153.123 в 04:49, 1 сентября 2022

2022-09-01T04:49:54Z

194.85.161.2 в 22:05, 7 июня 2012

2012-06-07T22:05:06Z

194.85.161.2 в 21:39, 7 июня 2012

2012-06-07T21:39:11Z

194.85.161.2 в 20:44, 7 июня 2012

2012-06-07T20:44:17Z

178.178.20.180 в 19:31, 7 июня 2012

2012-06-07T19:31:05Z

194.85.161.2 в 18:44, 7 июня 2012

2012-06-07T18:44:18Z

194.85.161.2 в 23:41, 6 июня 2012

2012-06-06T23:41:50Z

194.85.161.2 в 21:49, 6 июня 2012

2012-06-06T21:49:59Z

194.85.161.2 в 12:33, 6 июня 2012

2012-06-06T12:33:20Z

← Предыдущая		Версия 16:27, 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 Майкл Наки].
−	\|}
−
	{{Лемма		{{Лемма
	\|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.		\|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.

← Предыдущая		Версия 04:49, 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 Майкл Наки].
		+	\|}
		+
	{{Лемма		{{Лемма
	\|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.		\|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.

@@ Строка 3: / Строка 3: @@
 |proof=
 Пусть нам дана формула <tex>\phi</tex> с <tex>n</tex> переменными.<br>
-Попобуем построить схемы <tex>C_n^1, \ldots, C_n^n</tex>, работающие следующим образом:
+Попробуем построить схемы <tex>C_n^1, \ldots, C_n^n</tex>, работающие следующим образом:
 *<tex>C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1</tex>;
 *<tex> \ldots </tex>

@@ Строка 31: / Строка 31: @@
 Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
 Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 </tex>, тогда <tex>\nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex>. <br>
-Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
+Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>. Значит, <tex>\mathrm{\Pi_2} \subset \mathrm{\Sigma_2} </tex>.<br>
 }}
 [[Категория: Теория сложности]]

@@ Строка 30: / Строка 30: @@
 *<tex>L_1 \subset L</tex>
 Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
-Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 </tex>, тогда <tex>\nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex> <br>
+Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 </tex>, тогда <tex>\nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex>. <br>
 Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
 }}
 [[Категория: Теория сложности]]

@@ Строка 19: / Строка 19: @@
 Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
 |proof=
-Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y \ \exists z : |y|,|z| \le p(|x|), p \in poly, \phi(x, y, z)\}</tex>.<br>
+Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>: <tex> \exists p \in poly, \phi \in \mathrm{\widetilde{P}}, \forall x  \in L  \Leftrightarrow \forall y \ \exists z : |y|,|z| \le p(|x|), \phi(x, y, z) = 1</tex>.<br>
-Для фиксированного <tex>x</tex> <tex>\phi</tex> можно рассмтривать как формулу с <tex>n</tex> битовыми переменныии (так как мы знаем, что <tex>\phi \in \mathrm{P}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>), где <tex>n</tex> {{---}} полином от длины входа <tex>x</tex> (из-за ограничений накладываемых по определению класса <tex>\mathrm{\Pi_2}</tex> на <tex>|y|, |z|)</tex>.
+Для фиксированного <tex>x</tex> <tex>\phi</tex> можно рассматривать как формулу с <tex>n</tex> битовыми переменными (так как мы знаем, что <tex>\phi \in \mathrm{\widetilde{P}}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>), где <tex>n</tex> {{---}} полином от длины входа <tex>x</tex> (из-за ограничений накладываемых по определению класса <tex>\mathrm{\Pi_2}</tex> на <tex>|y|, |z|)</tex>.
 Для заданных <tex>x</tex> и <tex>y</tex> научимся находить такой <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если это возможно. Подставим значения <tex>x</tex> и <tex>y</tex> в формулу <tex>\phi</tex>. Теперь <tex>\phi</tex> зависит только от <tex>z</tex>: <tex>\phi_{xy}(z)</tex>.
-Из предыдущей леммы мы установили существования семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_{p(|x|)}</tex> на <tex>\phi_{xy}</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>,  или же последовательность нулей. <br>
+Из предыдущей леммы мы установили существования семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_{p(|x|)}</tex> на <tex>\phi_{xy}</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z) </tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>,  или же последовательность нулей. <br>
-Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_{p(|x|)}(\phi_{xy}))\}</tex>.<br>
+Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_{p(|x|)}(\phi_{xy})) = 1\}</tex>.<br>
-Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy}))\}</tex>. <br>
+Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. <br>
 Покажем, что <tex>L=L_1</tex>:
 *<tex> L \subset L_1</tex><br>
@@ Строка 30: / Строка 30: @@
 *<tex>L_1 \subset L</tex>
 Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
-Пусть <tex>\exists y \ \forall z \ \phi(x,y,z)=0 \Rightarrow \nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex> {{---}} очевидно.<br>
+Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 </tex>, тогда <tex>\nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex> <br>
-Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy}))\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
+Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
 }}
 [[Категория: Теория сложности]]

@@ Строка 1: / Строка 1: @@
 {{Лемма
-|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной функции <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.
+|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.
 |proof=
-Пусть нам дана функция <tex>\phi</tex> с <tex>n</tex> переменными.<br>
+Пусть нам дана формула <tex>\phi</tex> с <tex>n</tex> переменными.<br>
-Определим схемы <tex>C_n^1, \ldots, C_n^n</tex> следующим образом:
+Попобуем построить схемы <tex>C_n^1, \ldots, C_n^n</tex>, работающие следующим образом:
 *<tex>C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1</tex>;
 *<tex> \ldots </tex>
@@ Строка 9: / Строка 9: @@
 *<tex> \ldots </tex>
 *<tex>C_n^n(\phi, b_1, \ldots, b_{n - 1}) = 1 \Leftrightarrow \phi(b_1, \ldots, b_{n-1}, 1)=1</tex>.
-Задача определения возврщаемого значения таких схем {{---}} задача <tex>\mathrm{SAT}</tex>. По условию <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>, следовательно, такие схемы существуют и каждая из них будет полиномиального размера. Рассмотрим последовательность: <tex>b_1=C_n^1(\phi), b_2=C_n^2(\phi, b1), \ldots, b_n=C_n^n(\phi, b_1, \ldots, b_{n-1})</tex>. Очевидно, что это будет последовательностью бит, которая удовлетворит <tex>\phi</tex>, или же последовательностью нулей, если <tex>\phi</tex> удовлетворить нельзя, ее и нужно вернуть. В итоге мы получили схему полиномиального размера <tex>C_n(\phi)</tex>.
+Задача определения возвращаемого значения таких схем тогда будет эквивалентна задаче <tex>\mathrm{SAT}</tex>. По условию <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>, следовательно, такие схемы существуют и каждая из них будет полиномиального размера. Рассмотрим последовательность: <tex>b_1=C_n^1(\phi), b_2=C_n^2(\phi, b1), \ldots, b_n=C_n^n(\phi, b_1, \ldots, b_{n-1})</tex>. Очевидно, что это будет последовательностью бит, которая удовлетворит <tex>\phi</tex>, или же последовательностью нулей, если <tex>\phi</tex> удовлетворить нельзя. Если при <tex>b_1=1</tex> формулу <tex>\phi</tex> удовлетворить возможно, то есть <tex>C_n^1(\phi)=1</tex>, то нужно взять <tex>b_1=1</tex>, если же нет, если <tex>C_n^1(\phi)=0</tex>, тогда имеет смысл искать следующие биты последовательности, удовлетворяющей <tex>\phi</tex> только при <tex>b_1=0</tex>. Следующие биты последовательности выбираются по аналогии. <br>
 }}
@@ Строка 18: / Строка 19: @@
 Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
 |proof=
-Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y \ \exists z \ \phi(x, y, z)\}</tex>.<br>
+Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y \ \exists z : |y|,|z| \le p(|x|), p \in poly, \phi(x, y, z)\}</tex>.<br>
-<tex>\phi</tex> можно рассмтривать как функцию с <tex>n</tex> битовыми переменныии (так как мы знаем, что <tex>\phi \in \mathrm{P}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>), где <tex>n</tex> {{---}} полином от длины входа <tex>x</tex> (из-за ограничений накладываемых по определению класса <tex>\mathrm{\Pi_2}</tex> на <tex>|y|, |z|)</tex>.
+Для фиксированного <tex>x</tex> <tex>\phi</tex> можно рассмтривать как формулу с <tex>n</tex> битовыми переменныии (так как мы знаем, что <tex>\phi \in \mathrm{P}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>), где <tex>n</tex> {{---}} полином от длины входа <tex>x</tex> (из-за ограничений накладываемых по определению класса <tex>\mathrm{\Pi_2}</tex> на <tex>|y|, |z|)</tex>.
-Для заданных <tex>x</tex> и <tex>y</tex> научимся находить такой <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если это возможно. Подставим значения <tex>x</tex> и <tex>y</tex> в функцию <tex>\phi</tex>. Теперь <tex>\phi</tex> зависит только от <tex>z</tex>: <tex>\phi_{xy}(z)</tex>.
+Для заданных <tex>x</tex> и <tex>y</tex> научимся находить такой <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если это возможно. Подставим значения <tex>x</tex> и <tex>y</tex> в формулу <tex>\phi</tex>. Теперь <tex>\phi</tex> зависит только от <tex>z</tex>: <tex>\phi_{xy}(z)</tex>.
-Из предыдущей леммы мы получили семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_m</tex> на <tex>\phi_{xy}</tex>, где <tex>m=n-|x|-|y|</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>,  или же последовательность нулей. <br>
+Из предыдущей леммы мы установили существования семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_{p(|x|)}</tex> на <tex>\phi_{xy}</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>,  или же последовательность нулей. <br>
-Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_m(\phi_{xy}))\}</tex>.<br>
+Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_{p(|x|)}(\phi_{xy}))\}</tex>.<br>
 Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy}))\}</tex>. <br>
 Покажем, что <tex>L=L_1</tex>:
 *<tex> L \subset L_1</tex><br>
-Очевидно. Можно за <tex>G</tex> взять <tex>C_m</tex>.
+Очевидно. Можно за <tex>G</tex> взять <tex>C_{p(|x|)}</tex>.
 *<tex>L_1 \subset L</tex>
 Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>