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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:04Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:11, 1 сентября 2022

2022-09-01T04:11:48Z

188.227.78.144: /* Теорема */

2013-06-04T13:20:56Z

‎Теорема

Shevchen в 09:45, 5 июня 2012

2012-06-05T09:45:21Z

Shevchen в 09:35, 5 июня 2012

2012-06-05T09:35:03Z

Shevchen в 13:00, 4 июня 2012

2012-06-04T13:00:10Z

Igor buzhinsky в 22:17, 3 июня 2012

2012-06-03T22:17:09Z

Kirelagin в 13:13, 3 июня 2012

2012-06-03T13:13:36Z

Kirelagin в 13:13, 3 июня 2012

2012-06-03T13:13:04Z

Kirelagin в 13:11, 3 июня 2012

2012-06-03T13:11:34Z

← Предыдущая		Версия 16:35, 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 Майкл Наки].
−	\|}
−
	'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P\|P]] не совпадает с [[Класс NP\|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота\|NP-полным]].		'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P\|P]] не совпадает с [[Класс NP\|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота\|NP-полным]].

← Предыдущая		Версия 04:11, 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 Майкл Наки].
		+	\|}
		+
	'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P\|P]] не совпадает с [[Класс NP\|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота\|NP-полным]].		'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P\|P]] не совпадает с [[Класс NP\|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота\|NP-полным]].

@@ Строка 79: / Строка 79: @@
   for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>
-    if <tex>x \in \mathrm{SAT}</tex> and <tex>[g(|x|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \not \in \mathrm{SAT}]</tex>
+    if <tex>x \in \mathrm{SAT}</tex> and <tex>[g(|f_i(x)|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \not \in \mathrm{SAT}]</tex>
       <tex>g(n+1) := g(n)+1</tex>
       return
-    if <tex>x \not \in \mathrm{SAT}</tex> and <tex>[g(|x|) \equiv 0 \pmod{2}</tex> and <tex>f_i(x) \in \mathrm{SAT}]</tex>
+    if <tex>x \not \in \mathrm{SAT}</tex> and <tex>[g(|f_i(x)|) \equiv 0 \pmod{2}</tex> and <tex>f_i(x) \in \mathrm{SAT}]</tex>
       <tex>g(n+1) := g(n)+1</tex>
       return

@@ Строка 101: / Строка 101: @@
 === Время работы алгоритма ===
-Проверим выполнение первого свойства языка <tex>L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>.
+Проверим выполнение первого свойства языка <tex>L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>. Покажем, что <tex>T(g, n)</tex> отличается от <tex>T(g, n - 1)</tex> не более, чем на неубывающий полином <tex>p(n)</tex>. Из этого будет следовать полиномиальность <tex>g</tex>: <tex>T(g, n) \le p(n) + p(n - 1) + \ldots + p(1) \le n p(n) \in poly(n)</tex>.
 Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.

← Предыдущая		Версия 09:35, 5 июня 2012
Строка 1:		Строка 1:
	'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P\|P]] не совпадает с [[Класс NP\|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота\|NP-полным]].		'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P\|P]] не совпадает с [[Класс NP\|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота\|NP-полным]].
		+
		+	== Иллюстрация ==
		+
		+	Определим язык <tex>A</tex> как множество таких формул <tex>\alpha</tex>,
		+	что <tex>\left\lfloor \frac{1}{2}\log_{10}^*\|\alpha\|\right\rfloor</tex> чётно.
		+	Иными словами, <tex>A</tex> — это язык формул с длинами, лежащими в промежутках
		+	<tex>\left[1,10^{10}\right),
		+	\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4,
		+	\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots</tex>
		+	Далее будем обозначать <tex>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</tex>
		+	как <tex>^{n}a</tex>.
		+
		+	Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в <tex>A</tex>,
		+	так и в <tex>\bar{A}</tex> лежит бесконечное множество элементов из <tex>\mathrm{SAT}</tex>,
		+	не распознаваемых за полиномиальное время, поэтому <tex>\mathrm{SAT} \cap A \not\in \mathrm{P}</tex>.
		+	Из <tex>A \in \mathrm{P}</tex> и <tex>\mathrm{SAT} \in \mathrm{NP}</tex> следует, что <tex>\mathrm{SAT} \cap A \in \mathrm{NP}</tex>.
		+
		+	Осталось показать, что <tex>\mathrm{SAT} \cap A</tex> не является NP-полным. Пусть
		+	это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
		+	[[Сведение по Карпу\|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT} \cap A</tex>.
		+
		+	Возьмём формулу <tex>\varphi</tex> длиной <tex>^{2k+1}10</tex>.
		+	Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT} \cap A</tex>.
		+	Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток
		+	<tex>\left[^{2k+2}10, ^{2k+4}10\right)</tex> или дальше, так как размер
		+	выхода полиномиальной функции не может быть экспоненциально больше длины
		+	входа. Значит, <tex>\varphi</tex> отображается в меньший промежуток, но
		+	в этом случае размер выхода экспоненциально меньше длины входа. Добавляя
		+	к этому то, что проверку на принадлежность <tex>f(\varphi)</tex> к
		+	<tex>\mathrm{SAT} \cap A</tex> можно осуществить за <tex>O(2^{poly})</tex>
		+	(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>), получаем программу,
		+	разрешающую <tex>\varphi</tex> за полином. Утверждение о том, что все формулы
		+	<tex>\varphi</tex> длиной <tex>^{2k+1}10</tex> принадлежат классу
		+	<tex>\mathrm{P}</tex>, скорее всего неверно, и, следовательно, язык
		+	<tex>\mathrm{SAT} \cap A</tex> не является NP-полным.
		+
		+	Заметим, что это объяснение не является доказательством!
		+
		+	== Теорема ==

	{{Теорема		{{Теорема

@@ Строка 26: / Строка 26: @@
 * Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов.
-* Пусть вычисленное значение <tex>g(n)</tex> чётно. Определим <tex>g(n+1)</tex> следующим образом:
+* Пусть вычисленное значение <tex>g(n) = 2 i</tex>. Определим <tex>g(n+1)</tex> следующим образом:
   for <tex>x</tex> : <tex>|x| \le \log_2 n</tex>
@@ Строка 37: / Строка 37: @@
   <tex>g(n+1) := g(n)</tex>
-* Пусть вычисленное значение <tex>g(n)</tex> нечётно. Определим <tex>g(n+1)</tex> следующим образом:
+* Пусть вычисленное значение <tex>g(n) = 2 i - 1</tex>. Определим <tex>g(n+1)</tex> следующим образом:
   for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>
@@ Строка 69: / Строка 69: @@
 <ul>
-<li>для случая <tex>g(n) \equiv 0 \pmod{2}</tex>:<br/>
+<li>для случая <tex>g(n) = 2 i</tex>:<br/>
 <tex>\parbox{0px}{
 \begin{align*}
@@ Строка 81: / Строка 81: @@
 </li>
-<li>для случая <tex>g(n) \equiv 1 \pmod{2}</tex>:<br/>
+<li>для случая <tex>g(n) = 2 i - 1</tex>:<br/>
 <tex>\parbox{0px}{
 \begin{align*}

@@ Строка 4: / Строка 4: @@
 |author=Ладнер
 |statement=
-<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>
+<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>.
 |proof=
 Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что никакой <tex>\mathrm{NP}</tex>-полный язык (например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям:

@@ Строка 102: / Строка 102: @@
 <tex>c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4</tex>.
-Тогда, в силу <tex>T(g, 1) = d \le c \cdot 1^4</tex> и неравенства выше, по индукции легко доказать, что <tex>T(g, n)</tex> ограничено сверху <tex>c n^4</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
+Тогда, в силу <tex>T(g, 1) = d \le c \cdot 1^4</tex> и неравенства строкой выше, по индукции легко доказать, что <tex>T(g, n)</tex> ограничено сверху <tex>c n^4</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
 }}