Класс NP - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-01T08:44:15Z

rollbackEdits.php mass rollback

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

2022-09-01T03:15:48Z

Yoprst: Исправлена опечатка в формуле: l переименована в x

2020-10-04T11:22:32Z

Исправлена опечатка в формуле: l переименована в x

Infovarius в 10:06, 14 ноября 2018

2018-11-14T10:06:08Z

192.168.0.2 в 07:30, 17 июня 2010

2010-06-17T07:30:54Z

Ulyantsev в 16:48, 2 июня 2010

2010-06-02T16:48:22Z

192.168.0.2: /* Класс \Sigma_1 */

2010-05-29T13:16:06Z

‎Класс \Sigma_1

Perovskaya в 16:07, 18 марта 2010

2010-03-18T16:07:44Z

Perovskaya в 16:07, 18 марта 2010

2010-03-18T16:07:30Z

Perovskaya в 15:50, 18 марта 2010

2010-03-18T15:50:50Z

← Предыдущая		Версия 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 Майкл Наки].
−	\|}
−
	В теории сложности '''Класс NP''' — класс языков (задач), ответ на которые можно проверить за полиномиальное время.		В теории сложности '''Класс NP''' — класс языков (задач), ответ на которые можно проверить за полиномиальное время.

← Предыдущая		Версия 03:15, 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 Майкл Наки].
		+	\|}
		+
	В теории сложности '''Класс NP''' — класс языков (задач), ответ на которые можно проверить за полиномиальное время.		В теории сложности '''Класс NP''' — класс языков (задач), ответ на которые можно проверить за полиномиальное время.

@@ Строка 11: / Строка 11: @@
 Будем говорить, что <tex>y</tex> является сертификатом принадлежности <tex>x</tex> языку <tex>L</tex>, если существует полиномиальное отношение (верификатор) <tex>R</tex>, такое что <tex>R(x,y)=1</tex> тогда и только тогда, когда <tex>x</tex> принадлежит <tex>L</tex>.
-Классом <tex>\Sigma_1</tex> называется класс языков (задач) <tex>L</tex>, таких что для каждого из них существует полиномиальный верификатор <tex>R</tex>, а также полином <tex>p</tex>, такие что слово <tex>l</tex> принадлежит языку <tex>L</tex> тогда и только тогда, когда существует сертификат <tex>y</tex>, длина которого не превосходит заданного полинома <tex>p</tex>, и сертификат <tex>y</tex> удовлетворяет верификатору <tex>R</tex>.
+Классом <tex>\Sigma_1</tex> называется класс языков (задач) <tex>L</tex>, таких что для каждого из них существует полиномиальный верификатор <tex>R</tex>, а также полином <tex>p</tex>, такие что слово <tex>x</tex> принадлежит языку <tex>L</tex> тогда и только тогда, когда существует сертификат <tex>y</tex>, длина которого не превосходит заданного полинома <tex>p</tex>, и сертификат <tex>y</tex> удовлетворяет верификатору <tex>R</tex>.
-<tex>\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex>
+<tex>\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | x \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex>
 ==Теорема о равенстве <tex>\Sigma_1 </tex> и <tex> NP</tex>==

← Предыдущая		Версия 10:06, 14 ноября 2018
Строка 37:		Строка 37:
	* Задача о [[NP-полнота задач о вершинном покрытии, клике и независимом множестве\|вершинном покрытии, клике и независимом множестве]].		* Задача о [[NP-полнота задач о вершинном покрытии, клике и независимом множестве\|вершинном покрытии, клике и независимом множестве]].
	* Задача о [[NP-полнота задачи о выполнимости булевой формулы в форме КНФ\|удовлетворении булевой формулы, заданной в КНФ]]. SAT		* Задача о [[NP-полнота задачи о выполнимости булевой формулы в форме КНФ\|удовлетворении булевой формулы, заданной в КНФ]]. SAT
		+
		+	[[Category:NP]]

@@ Строка 19: / Строка 19: @@
 <tex>\Sigma_1</tex> = '''NP'''
 ===Доказательство===
-Построим доказательство равенство из доказательств двух взаимных включений.
+Построим доказательство равенства из доказательств двух взаимных включений.
 <tex>\Sigma_1</tex> &sub; '''NP'''

@@ Строка 1: / Строка 1: @@
-В теории сложности '''Класс''' <tex>NP</tex> &mdash; класс языков (задач), ответ на которые можно проверить за полиномиальное время.
+В теории сложности '''Класс NP''' &mdash; класс языков (задач), ответ на которые можно проверить за полиномиальное время.
 ===Определение===
-Определение класса NP через [[Класс NTIME|класс NTIME]] и [[Класс NSPACE|класс NSPACE]].
+Формальное определение класса '''NP''' через класс '''[[NTIME]]''' выглядит так:
-<tex>NP=\bigcup_{i=0}^{\infty} NTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} NTIME(in^k)</tex>
+'''NP'''=<tex>\bigcup_{i=0}^{\infty}</tex> '''NTIME'''<tex>(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty}</tex> '''NTIME'''<tex>(in^k)</tex>
 ===Класс <tex>\Sigma_1</tex>===
-Альтернативным определением класса <tex>NP</tex> является определение на языке сертификатов.
+Альтернативным определением класса '''NP''' является определение на языке сертификатов.
 Будем говорить, что <tex>y</tex> является сертификатом принадлежности <tex>x</tex> языку <tex>L</tex>, если существует полиномиальное отношение (верификатор) <tex>R</tex>, такое что <tex>R(x,y)=1</tex> тогда и только тогда, когда <tex>x</tex> принадлежит <tex>L</tex>.
@@ Строка 17: / Строка 17: @@
 ==Теорема о равенстве <tex>\Sigma_1 </tex> и <tex> NP</tex>==
 ===Формулировка===
-<tex>\Sigma_1 = NP</tex>
+<tex>\Sigma_1</tex> = '''NP'''
 ===Доказательство===
 Построим доказательство равенство из доказательств двух взаимных включений.
-<tex>\Sigma_1 \subset NP</tex>
+<tex>\Sigma_1</tex> &sub; '''NP'''
-Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в <tex>NP</tex>.
+Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1</tex> в '''NP'''.
 Вхождение доказано.
-<tex>NP \subset \Sigma_1</tex>
+'''NP''' &sub; <tex>\Sigma_1</tex>
-Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
+Пусть <tex>L</tex> &isin; '''NP''' . Тогда существует НМТ <tex>m</tex>, распознающая <tex>L</tex>. Построим сертификат <tex>y</tex> как последовательность недетерминированных выборов машины <tex>m</tex>, приводящих к допуску слова. Верификатором сертификата <tex>R</tex> выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
 Теорема доказана.

@@ Строка 9: / Строка 9: @@
 Альтернативным определением класса <tex>NP</tex> является определение на языке сертификатов.
-Будем говорить, что <tex>y</tex> является сертификатом принадлежности <tex>x</tex> языку <tex>L</tex>, если существует полиномиальное отношение (верификатор) <tex>R</tex>, такое что <tex>R(x,y)=1</tex> тогда и только тогда, когда</tex>x</tex> принадлежит <tex>L</tex>.
+Будем говорить, что <tex>y</tex> является сертификатом принадлежности <tex>x</tex> языку <tex>L</tex>, если существует полиномиальное отношение (верификатор) <tex>R</tex>, такое что <tex>R(x,y)=1</tex> тогда и только тогда, когда<tex>x</tex> принадлежит <tex>L</tex>.
 Классом <tex>\Sigma_1</tex> называется класс языков (задач) <tex>L</tex>, таких что для каждого из них существует полиномиальный верификатор <tex>R</tex>, а также полином <tex>p</tex>, такие что слово <tex>l</tex> принадлежит языку <tex>L</tex> тогда и только тогда, когда существует сертификат <tex>y</tex>, длина которого не превосходит заданного полинома <tex>p</tex>, и сертификат <tex>y</tex> удовлетворяет верификатору <tex>R</tex>.

← Предыдущая		Версия 15:50, 18 марта 2010
Строка 32:		Строка 32:

	Теорема доказана.		Теорема доказана.
−
−	~~==Теорема о равенстве <tex>\Pi_1 </tex> и <tex> NP</tex>==~~
−	~~<tex>NP = \Pi_1</tex> (См. [[Полиномиальная иерархия]])~~

	==Примеры задач класса NP==		==Примеры задач класса NP==