Теорема Бермана — Форчуна - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:10:52Z

rollbackEdits.php mass rollback

185.220.100.252 в 06:09, 1 сентября 2022

2022-09-01T06:09:11Z

Komarov: это вообще кто-нибудь проверял?

2013-06-04T15:02:27Z

это вообще кто-нибудь проверял?

AndrewD в 16:27, 4 июня 2012

2012-06-04T16:27:51Z

AndrewD в 16:18, 4 июня 2012

2012-06-04T16:18:38Z

194.85.161.2: /* См. также */

2012-06-04T13:46:11Z

‎См. также

AndrewD в 10:05, 3 июня 2012

2012-06-03T10:05:40Z

Kirelagin в 08:14, 3 июня 2012

2012-06-03T08:14:51Z

Kirelagin в 08:06, 3 июня 2012

2012-06-03T08:06:32Z

AndrewD в 22:49, 2 июня 2012

2012-06-02T22:49:02Z

← Предыдущая		Версия 16:10, 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 Майкл Наки].
−	\|}
−
	{{Лемма		{{Лемма
	\|about=1		\|about=1

← Предыдущая		Версия 06:09, 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 Майкл Наки].
		+	\|}
		+
	{{Лемма		{{Лемма
	\|about=1		\|about=1

@@ Строка 48: / Строка 48: @@
   <tex>check(\phi, i)</tex>:
       '''if''' <tex>\phi=0</tex>
-          '''return''' 0
+          '''exit''' 0
       '''if''' <tex>\phi=1</tex>
           '''return''' 1

@@ Строка 57: / Строка 57: @@
           '''exit''' <tex>0</tex>
       '''return''' <tex>memo[f(\phi)]</tex>
-[[Файл:Berman-Fortune.png|thumb|right|Двоичное дерево, получающееся в результате рекурсивных вызовов модифицированной программы. Красным и желтым помечены узлы, в которых происходит обращение к элементу ''memo[j]''. В красных узлах условие ''(1)'' ложно, в желтых {{---}} истинно.]]
+[[Файл:Berman-Fortune.png|thumb|upright=2.0|Двоичное дерево, получающееся в результате рекурсивных вызовов модифицированной программы. Красным и желтым помечены узлы, в которых происходит обращение к элементу ''memo[j]''. В красных узлах условие ''(1)'' ложно, в желтых {{---}} истинно.]]
 Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы.

@@ Строка 57: / Строка 57: @@
           '''exit''' <tex>0</tex>
       '''return''' <tex>memo[f(\phi)]</tex>
 Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы.
-Рассмотрим произвольный элемент <tex>memo[i]</tex>. Найдем, сколько раз условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[i]</tex>. Найдем в дереве такой узел, в котором есть обращение к <tex>memo[i]</tex>, а в его поддереве обращений к этому элементу нет, причем <tex>memo[i] = -1</tex>. До этого момента количество обращений к <tex>memo[i]</tex> не превышает глубины найденного узла, что не превосходит высоты дерева, что не превосходит некоторого полинома <tex>p'(n)</tex>. После этого момента условие <tex>(1)</tex> будет принимать истинное значение при обращении к <tex>memo[i]</tex>. Значит, в ходе выполнения программы условие <tex>(1)</tex> является ложным при обращении к <tex>memo[i]</tex> не более <tex>p'(n)</tex> раз.
+Рассмотрим произвольный элемент <tex>memo[j]</tex>. Найдем, сколько раз условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[j]</tex>. Найдем в дереве такой узел, в котором есть обращение к <tex>memo[j]</tex>, а в его поддереве обращений к этому элементу нет, причем <tex>memo[j] = -1</tex>. До этого момента количество обращений к <tex>memo[j]</tex> не превышает глубины найденного узла, что не превосходит высоты дерева, что не превосходит некоторого полинома <tex>p'(n)</tex>. После этого момента условие <tex>(1)</tex> будет принимать истинное значение при обращении к <tex>memo[j]</tex>. Значит, в ходе выполнения программы условие <tex>(1)</tex> является ложным при обращении к <tex>memo[j]</tex> не более <tex>p'(n)</tex> раз.
 Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>p''(n) = r(n) \cdot p'(n)</tex> раз, то есть <tex>p''</tex> {{---}} полином. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>p''(n)</tex> раз, а значит в дереве не более <tex>p''(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot p''(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.

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

@@ Строка 12: / Строка 12: @@
 {{Определение
 |definition=
-<tex>\mathrm{TAUT} = \{\phi</tex> {{---}} булева формула <tex>| \forall x = (x_1, x_2, \ldots , x_m) \, \phi(x)=1\}</tex>.
+<tex>\mathrm{TAUT} = \{\phi</tex> {{---}} булева формула <tex>\bigm{|} \forall x = (x_1, x_2, \ldots , x_m) \, \phi(x)=1\}</tex>.
 }}
@@ Строка 18: / Строка 18: @@
 |about=2
 |statement=<tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>.
-|proof=<tex>\overline {\mathrm{TAUT}} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in \mathrm{SAT}\}</tex>, то есть <tex>\mathrm{SAT} \le \overline {\mathrm{TAUT}} \, (f(\phi) = \overline {\phi})</tex>. Кроме того, <tex>\overline {\mathrm{TAUT}} \in \mathrm{NP}</tex> <tex>(</tex>в качестве сертификата используется <tex>x</tex>, на котором <tex>\phi(x) \ne 1)</tex>. Значит <tex>\overline{\mathrm{TAUT}} \in \mathrm{NPC}</tex>. Тогда по лемме (1) <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>.
+|proof=<tex>\overline {\mathrm{TAUT}} = \{\phi \bigm{|} \exists x : \phi(x) \ne 1\} = \{\phi \bigm{|} \overline {\phi} \in \mathrm{SAT}\}</tex>, то есть <tex>\mathrm{SAT} \le \overline {\mathrm{TAUT}} \, (f(\phi) = \overline {\phi})</tex>. Кроме того, <tex>\overline {\mathrm{TAUT}} \in \mathrm{NP}</tex> <tex>(</tex>в качестве сертификата используется <tex>x</tex>, на котором <tex>\phi(x) \ne 1)</tex>. Значит <tex>\overline{\mathrm{TAUT}} \in \mathrm{NPC}</tex>. Тогда по лемме (1) <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>.
 }}
 {{Определение
 |definition=
-<tex>\mathrm{SPARSE} = \{L | \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</tex>.
+<tex>\mathrm{SPARSE} = \{L \bigm{|} \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</tex>.
 }}
@@ Строка 33: / Строка 33: @@
 Для начала напишем программу, разрешающую <tex>\mathrm{TAUT}</tex>:
   <tex>check(\phi, i)</tex>:
-      '''if''' <tex>\phi=0</tex>
+     '''if''' <tex>\phi=0</tex>
           '''return''' 0
-      '''if''' <tex>\phi=1</tex>
+     '''if''' <tex>\phi=1</tex>
           '''return''' 1
-      '''if''' <tex>memo[\phi] \ne -1</tex>
+     '''if''' <tex>memo[\phi] \ne -1</tex>
           '''return''' <tex>memo[\phi]</tex>
-    <tex>memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)</tex>
+     <tex>memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)</tex>
       '''return''' <tex>memo[\phi]</tex>
 Ответом будет <tex>check(\phi, 1)</tex>.
@@ Строка 53: / Строка 53: @@
       '''if''' <tex>memo[f(\phi)] \ne -1</tex>        //(1)
           '''return''' <tex>memo[f(\phi)]</tex>
-    <tex>memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)</tex>        //(2)
+     <tex>memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)</tex>        //(2)
       '''if''' <tex>memo.size() > r(n)</tex>
           '''exit''' <tex>0</tex>
@@ Строка 59: / Строка 59: @@
 Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы.
-Рассмотрим произвольный элемент <tex>memo[i]</tex>. Заметим, что условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[i]</tex> не более одного раза. Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>r(n)</tex> раз. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>r(n)</tex> раз, а значит в дереве не более <tex>r(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot r(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.
+Рассмотрим произвольный элемент <tex>memo[i]</tex>. Найдем, сколько раз условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[i]</tex>. Найдем в дереве такой узел, в котором есть обращение к <tex>memo[i]</tex>, а в его поддереве обращений к этому элементу нет, причем <tex>memo[i] = -1</tex>. До этого момента количество обращений к <tex>memo[i]</tex> не превышает глубины найденного узла, что не превосходит высоты дерева, что не превосходит некоторого полинома <tex>p'(n)</tex>. После этого момента условие <tex>(1)</tex> будет принимать истинное значение при обращении к <tex>memo[i]</tex>. Значит, в ходе выполнения программы условие <tex>(1)</tex> является ложным при обращении к <tex>memo[i]</tex> не более <tex>p'(n)</tex> раз.
 Итого, данная программа разрешает <tex>\mathrm{TAUT}</tex> за полиномиальное время. А так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>, то <tex>\mathrm{P}=\mathrm{coNP}</tex>, то есть <tex>\mathrm{coP}=\mathrm{coNP}</tex>, откуда <tex>\mathrm{P}=\mathrm{NP}</tex>.

@@ Строка 1: / Строка 1: @@
 {{Лемма
 |about=1
-|statement=Язык <tex>L</tex> является <tex>\mathrm{coNP}</tex>-полным тогда и только тогда, когда <tex>\overline L</tex> является <tex>\mathrm{NP}</tex>-полным.
+|statement=Язык <tex>L</tex> является <tex>\mathrm{coNP}</tex>-полным тогда и только тогда, когда <tex>\overline L</tex> является <tex>\mathrm{NP}</tex>-полным (то есть <tex>L \in \mathrm{coNP\mbox{-}C} \Leftrightarrow L \in \mathrm{co\mbox{-}NPC}</tex>).
 |proof=Пусть <tex>L</tex> {{---}} <tex>\mathrm{coNP}</tex>-полный. Тогда <tex>L \in \mathrm{coNP}</tex> и <tex>\overline L \in \mathrm{NP}</tex>.

@@ Строка 45: / Строка 45: @@
 Так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex> и <tex>S \in \mathrm{coNPC}</tex>, то <tex>\mathrm{TAUT} \le S</tex>, то есть <tex>\exists f \in \mathrm{\widetilde{P}} : \phi \in \mathrm{TAUT} \Leftrightarrow f(\phi) \in S</tex>. Поэтому, если в предыдущей программе заменить все обращения к <tex>memo[\phi]</tex>, на <tex>memo[f(\phi)]</tex>, то полученная программа по-прежнему будет разрешать <tex>\mathrm{TAUT}</tex>.
-Оценим необходимый размер <tex>memo</tex>. Можно считать, что <tex>\mathrm{T}(f, \phi) \le q(n)</tex>, где <tex>n = |\phi|</tex>, а <tex>q</tex> {{---}} монотонно возрастающий полином. Тогда <tex>|f(\phi)| \le q(n)</tex>. Так как <tex>S \in \mathrm{SPARSE}</tex>, то <tex>|S \cap \Sigma^k| \le p(k)</tex>, где <tex>p</tex> {{---}} полином. Можно считать, что <tex>p</tex> монотонно возрастает. Тогда размер <tex>memo</tex> можно оценить сверху: <tex>memo.size() \le \sum\limits_{i=0}^{q(n)}p(i) \le (1+q(n)) \cdot p(q(n)) \le r(n)</tex>, где <tex>r(n)</tex> {{---}} полином.
+Оценим необходимый размер <tex>memo</tex>. Можно считать, что <tex>\mathrm{T}(f, \phi) \le q(n)</tex>, где <tex>n = |\phi|</tex>, а <tex>q</tex> {{---}} монотонно возрастающий полином. Тогда <tex>|f(\phi)| \le q(n)</tex>. Так как <tex>S \in \mathrm{SPARSE}</tex>, то <tex>|S \cap \Sigma^k| \le p(k)</tex>, где <tex>p</tex> {{---}} полином. Можно считать, что <tex>p</tex> монотонно возрастает. Тогда размер <tex>memo</tex> (число слов длины не более <tex>q(n)</tex> в языке) можно оценить сверху: <tex>memo.size() \le \sum\limits_{i=0}^{q(n)}p(i) \le (1+q(n)) \cdot p(q(n)) \le r(n)</tex>, где <tex>r(n)</tex> {{---}} полином.
   <tex>check(\phi, i)</tex>:
       '''if''' <tex>\phi=0</tex>