Теорема Бейкера-Гилла-Соловэя - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-01T08:44:19Z

rollbackEdits.php mass rollback

185.220.100.241 в 03:20, 1 сентября 2022

2022-09-01T03:20:25Z

192.168.0.2 в 12:54, 17 июня 2010

2010-06-17T12:54:42Z

Diniska в 08:43, 16 июня 2010

2010-06-16T08:43:41Z

Diniska: /* Формулировка */

2010-06-16T08:43:01Z

‎Формулировка

Diniska в 07:58, 16 июня 2010

2010-06-16T07:58:56Z

Diniska: Новая страница: «==Формулировка == \exists{} оракулы A и B такие что P^A=NP^A P^B\ne{}NP^B 1)
2010-06-16T07:58:32Z

Новая страница: «==Формулировка == <tex>\exists{}</tex> оракулы <tex>A</tex> и <tex>B</tex> такие что <tex>P^A=NP^A</tex> <tex>P^B\ne{}NP^B</tex> 1) <te…»

Новая страница
==Формулировка ==
<tex>\exists{}</tex> оракулы <tex>A</tex> и <tex>B</tex> такие что

<tex>P^A=NP^A</tex>
<tex>P^B\ne{}NP^B</tex>

1) <tex>A</tex> - <tex>PS</tex>-полный язык (разрешимый на полиномиальной памяти)
<tex>NP^A=NPS=PS=P^A</tex>
2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>

← Предыдущая		Версия 08:44, 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 Майкл Наки].
−	\|}
−
	==Формулировка ==		==Формулировка ==
	<tex>\exists{}</tex> оракулы <tex>A</tex> и <tex>B</tex> такие что		<tex>\exists{}</tex> оракулы <tex>A</tex> и <tex>B</tex> такие что

← Предыдущая		Версия 03:20, 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 Майкл Наки].
		+	\|}
		+
	==Формулировка ==		==Формулировка ==
	<tex>\exists{}</tex> оракулы <tex>A</tex> и <tex>B</tex> такие что		<tex>\exists{}</tex> оракулы <tex>A</tex> и <tex>B</tex> такие что

← Предыдущая		Версия 12:54, 17 июня 2010
Строка 10:		Строка 10:

	2) <tex>B</tex>:<tex>L_B=\{x\|\exists{y}\subset{B}:\|x\|=\|y\|\}</tex>		2) <tex>B</tex>:<tex>L_B=\{x\|\exists{y}\subset{B}:\|x\|=\|y\|\}</tex>
		+
		+	Будем строить B такое, чтобы для всех М.Т. из Р с оракулом С, данная машина тьюринга "ошибалась" на входе некоторой длины, при ответе на вопрос, есть ли в B слово той же длины, что и вход.
		+
		+	Положим множество B пустым.
		+	1. Переберем все машины тьюринга. Их счетное множество, каждая работает за полином.
		+	2. Для текущей МТ найдем первую длину i, такую что для всех слов длины не менее i ни одна из уже отработавших МТ ничего не спрашивала про них у оракула.
		+	3. Опишем поведение подходящего оракула. Пусть, если МТ М запущена на длине i, и задает вопросы оракулу C. Если М спросит С про слово длины не менее i, С должен ответить 0, одновременно запомнив, что это слово никогда не должно оказаться в В. Если же М спросит про уже включенные в В слова, С должен ответить 1.
		+	4. Теперь заметим, что так как М работает за полином, а ни про одно слово из i ничего не известно, то М не успеет спросить про все слова длины i, их экспоненциальное количество, значит будет хотя бы одно слово длины i, про которое М не спросит. Теперь, если М ответит 1, то нужно чтобы в В не было ни одного слова длины i, иначе - добавим в B первое в лексикографическом порядке слово из В длины i, про которое М не спрашивала.
		+	5. вернемся на шаг 1.
		+
		+	готово, построено множество слов В, такое что ни одна машина тьюринга из P с оракулом не сможет разрешить, но очевидно, что это множество из NP с оракулом

@@ Строка 7: / Строка 7: @@
 )<tex>A</tex>=<tex>TQBF</tex>
-  <tex>NP^{TQBF}\subset{NPS^{TGBF}}=PS^{TQBF}=PS\subset{P^{TQBF}\subset{NP^{TQBF}}}</tex>
+  <tex>NP^{TQBF}\subset{NPS^{TQBF}}=PS^{TQBF}=PS\subset{P^{TQBF}\subset{NP^{TQBF}}}</tex>
 ) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>

@@ Строка 5: / Строка 5: @@
 <tex>P^B\ne{}NP^B</tex>
-) <tex>A</tex> - <tex>PS</tex>-полный язык (разрешимый на полиномиальной памяти)
+)<tex>A</tex>=<tex>TQBF</tex>
-<tex>NP^A=NPS=PS=P^A</tex>
 ) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>