Классы Sharp P, Sharp P-Complete - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:37:32Z

rollbackEdits.php mass rollback

185.220.101.2 в 04:00, 1 сентября 2022

2022-09-01T04:00:14Z

Infovarius в 13:05, 14 ноября 2018

2018-11-14T13:05:23Z

176.59.10.248: /* Класс #P */

2017-06-01T07:31:44Z

‎Класс #P

5.18.180.97: /* Класс #P */

2017-06-01T06:58:43Z

‎Класс #P

5.18.180.97: /* Класс #P */

2017-05-24T19:43:39Z

‎Класс #P

176.59.5.204: /* Примеры #P-Complete задач */

2017-05-23T10:45:09Z

‎Примеры #P-Complete задач

Veda: /* Примеры #P-Complete задач */

2017-05-04T19:34:41Z

‎Примеры #P-Complete задач

Veda: /* Примеры #P-Complete задач */

2017-05-04T19:33:25Z

‎Примеры #P-Complete задач

Veda: /* Примеры #P-Complete задач */

2017-05-04T19:31:27Z

‎Примеры #P-Complete задач

← Предыдущая		Версия 16:37, 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 Майкл Наки].
−	\|}
−
	== Класс #P ==		== Класс #P ==
	{{Определение		{{Определение

← Предыдущая		Версия 04:00, 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 Майкл Наки].
		+	\|}
		+
	== Класс #P ==		== Класс #P ==
	{{Определение		{{Определение

← Предыдущая		Версия 13:05, 14 ноября 2018
Строка 106:		Строка 106:
	*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]		*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]

−	[[Категория: ~~Теория~~ сложности]]	+	[[Категория:Классы сложности]]

@@ Строка 12: / Строка 12: @@
 <tex>f : \{0,1\}^*  \rightarrow \mathbb{N}</tex> принадлежит <tex>FP</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время '''детерминированная''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* </tex> выполняется <tex> f(x) = M(x)</tex>.
 }}
-Вопрос, являются ли задачи из <tex>\#P</tex> эффективно разрешимыми, остается открытым. Подсчет числа сертификатов как минимум столь же сложен, как и проверка наличия сертификата, а значит, если доказать равенство <tex>\#P=FP</tex>, то автоматически будет доказано <tex>NP=P</tex>. Однако из  <tex>NP=P</tex> вовсе не следует  <tex>\#P=FP</tex>. Также можно заметить, что если  <tex>PSPACE  = P</tex>, то  <tex>\#P=FP</tex>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.
+Вопрос, являются ли задачи из <tex>\#P</tex> эффективно разрешимыми, остается открытым. Подсчет числа сертификатов как минимум столь же сложен, как и проверка наличия сертификата, а значит, если, доказать равенство <tex>\#P=FP</tex>, то автоматически будет доказано <tex>NP=P</tex>. Однако, из  <tex>NP=P</tex> вовсе не следует  <tex>\#P=FP</tex>. Также можно заметить, что если  <tex>PSPACE  = P</tex>, то  <tex>\#P=FP</tex>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.
 == Примеры задач из #P ==

@@ Строка 1: / Строка 1: @@
 == Класс #P ==
 {{Определение
-  |definition ='''Класс''' <tex>\#P-</tex>  класс задач подсчета, решением которых является количество успешных (завершающихся в допускающих состояниях) путей вычислений для '''недетерминированной''' МТ, работающей за полиномиальное время. Отличается от большинства рассмотренных классов тем, что задачи требуют в качестве ответа не  <tex>``0"</tex> или <tex>``1"</tex>, а натуральное число.
+  |definition = <tex>f : \{0,1\}^*  \rightarrow \mathbb{N}</tex> принадлежит <tex>\#P</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* : f(x) = | \{y \in \{0,1\}^{p(|x|)} : M(x,y) = 1 \} |</tex>.
-<br> Более формально: <tex>f : \{0,1\}^*  \rightarrow \mathbb{N}</tex> принадлежит <tex>\#P</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время '''недетерминированная''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* : f(x) = | \{y \in \{0,1\}^{p(|x|)} : M(x,y) = 1 \} |</tex>.
+}}
 }}
 {{Определение
   |definition ='''Класс''' <tex>\mathrm{FP}</tex> {{---}} класс задач подсчета, разрешимых на '''детерминированной''' машине Тьюринга за полиномиальное время, то есть:
-<tex>f : \{0,1\}^*  \rightarrow \mathbb{N}</tex> принадлежит <tex>FP</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время '''детерминированная''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* : f(x) = | \{y \in \{0,1\}^{p(|x|)} : M(x,y) = 1 \} |</tex>
+<tex>f : \{0,1\}^*  \rightarrow \mathbb{N}</tex> принадлежит <tex>FP</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время '''детерминированная''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* </tex> выполняется <tex> f(x) = M(x)</tex>.
 }}
 Вопрос, являются ли задачи из <tex>\#P</tex> эффективно разрешимыми, остается открытым. Подсчет числа сертификатов как минимум столь же сложен, как и проверка наличия сертификата, а значит, если доказать равенство <tex>\#P=FP</tex>, то автоматически будет доказано <tex>NP=P</tex>. Однако из  <tex>NP=P</tex> вовсе не следует  <tex>\#P=FP</tex>. Также можно заметить, что если  <tex>PSPACE  = P</tex>, то  <tex>\#P=FP</tex>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.

@@ Строка 62: / Строка 62: @@
 [[Файл:xor_block.png|thumb|200px|Блок XOR]]
 [[Файл:blocks_connection.png|thumb|200px|Блок XOR]]
-Задача нахождения перманента <tex>0,1-</tex>матрицы принадлежит классу <tex>\#P</tex>. Для вычисления перманента недетерминированно выбирается перестановка из <tex>n</tex> элементов и для каждой такой перестановки вычисляется произведение соответствующих элементов матрицы, полученные значения складываются. Время работы такого алгоритма на недетерминированной машине Тьюринга {{---}} <tex>O(n)</tex>.
+Задача нахождения перманента <tex>0,1-</tex>матрицы может быть сформулирована как задача подсчета количества перестановок, для которых произведение соответствующих элементов матрицы равно <tex>1</tex>. В такой формулировке задача нахождения перманента <tex>0,1-</tex>матрицы принадлежит классу <tex>\#P</tex> по определению.
 Докажем, что задача <tex>perm</tex> является <tex>\#P-</tex>полной. Нам известно, что задача <tex>\#SAT</tex> является <tex>\#P-</tex>полной. Аналогично задачам <tex>SAT</tex> и <tex>3SAT</tex> мы можем сказать, что задача <tex>\#SAT</tex> может быть сведена к задаче <tex>\#3SAT</tex>, которая также будет <tex>\#P-</tex>полной. Теперь сведем задачу <tex>\#3SAT</tex> к задаче <tex>perm</tex>.

@@ Строка 82: / Строка 82: @@
 Теперь сведем полученную матрицу к <tex>0,1-</tex>матрице. Для начала изменим веса ребер так, чтобы они были равны <tex>\pm1</tex>. Заметим, что замена ребра веса <tex>k</tex> на <tex>k</tex> параллельных ребер веса <tex>1</tex> не меняет перманента матрицы. В графе не допускаются параллельные ребра, но мы можем сделать их допустимыми, если разобьем каждое из них на два, добавив новые вершины. Чтобы избавиться от ребер с отрицательным весом, заметим, что перманент графа <tex>G</tex> с весами ребер равными <tex>\pm1</tex> равен числу из отрезка <tex>[-n!, \, n!]</tex> и может быть вычислен как <tex>y = x \,  ( mod \, 2^{m+1})</tex>, где <tex>m</tex> достаточно большое (например, <tex>m = n^2</tex>. Для того, чтобы вычислить <tex>y</tex>, достаточно посчитать перманент матрицы смежности графа, где все ребра веса <tex>-1</tex> заменены на ребра веса <tex>2^m</tex>. Эти ребра могут быть заменены на <tex>m</tex> ребер весом <tex>2</tex>, которые можно разбить на двойки параллельных ребер весом <tex>+1</tex>, как на предыдущем шаге.
-Таким образом для данной нам формулы мы за полиномиальное время построили соответствующий граф <tex>G'</tex> такой, что <tex>perm(A') = 4^m\cdot(\#\phi)</tex>, где <tex>A'</tex> - матрица смежности графа <tex>G'</tex> и свели задачу <tex>\#3SAT</tex> к задаче <tex>perm</tex>. Значит задача <tex>perm</tex> является <tex>\#P</tex>-полной.
+Таким образом для данной нам формулы мы за полиномиальное время построили соответствующий граф <tex>G'</tex> такой, что <tex>perm(A') = 4^m\cdot(\#\phi)</tex>, где <tex>A'</tex> - матрица смежности графа <tex>G'</tex> и свели задачу <tex>\#3SAT</tex> к задаче <tex>perm</tex>. Значит задача <tex>perm</tex> является <tex>\#P-</tex>полной.
 }}

@@ Строка 68: / Строка 68: @@
 По данной формуле <tex>\phi</tex> с <tex>n</tex> переменными и <tex>m</tex> клозами построим целочисленную матрицу <tex>A'</tex> такую, что <tex>perm(A')=4^m\cdot(\#\phi)</tex>, где <tex>\#\phi -</tex> количество удовлетворяющих подстановок для <tex>\phi</tex>. Для этого будем рассматривать матрицу <tex>A'</tex> как матрицу смежности двудольного графа <tex>G'</tex> : <tex>X = \{x_1 \ldots \, x_n\}, \,  \{x_i, x_j\} \in V(G) \iff A_{i, j} = 1</tex>. Таким образом, нашей целью будет построение некоторого графа <tex>G'</tex>, матрицей смежности которого будет <tex>A'</tex>.
-Для этого по данной 3-КНФ формуле построим ориентированный граф <tex>G'</tex> таким образом, чтобы в нем существовали покрытия циклами двух видов: те, которые соответствуют удовлетворяющим назначениям, и те, которые не соответствуют. Назовем покрытием ориентированного графа циклами такой подграф, что для любой вершины есть  ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда <tex>perm(A)</tex> равен сумме весов всех возможных покрытий циклами. Далее покажем, что любое удовлетворяющее назначение для формулы <tex>\phi</tex> будет добавлять <tex>4^m</tex> к <tex>perm(A')</tex>, а остальные не будут вносить вклад. Тогда <tex>perm(A')=4^m\cdot(\#\phi)</tex>.
+Для этого по данной 3-КНФ формуле построим ориентированный граф <tex>G'</tex> таким образом, чтобы в нем существовали покрытия циклами двух видов: те, которые соответствуют удовлетворяющим назначениям, и те, которые не соответствуют. Назовем покрытием ориентированного графа циклами такой подграф, что для любой вершины есть  ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда <tex>perm(A)</tex> равен сумме весов всех возможных покрытий циклами. Далее покажем, что любое удовлетворяющее назначение для формулы <tex>\phi</tex> будет добавлять <tex>4^m</tex> к <tex>perm(A')</tex>, а любое другое назначение не будет вносить вклад. Тогда <tex>perm(A')=4^m\cdot(\#\phi)</tex>.
 Построение графа <tex>G'</tex> выполним за полиномиальное время. Для этого будем использовать три вида блоков. (Все ребра, для которых на схеме не указан вес, имеют вес <tex>1</tex>.)

@@ Строка 80: / Строка 80: @@
 Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи XOR-блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменной, что аналогично присвоению переменной значения <tex>true</tex>. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначению формулы в 3-КНФ. А для каждого удовлетворяющего назначения существует множество циклов суммарным весом <tex>4^{3m}</tex>, так как они проходят через блоки XOR ровно <tex>3m</tex> раз. Таким образом <tex>perm(G') = 4^{3m}\cdot\#\phi</tex>.
-Теперь сведем полученную матрицу к <tex>0,1-</tex>матрице. Для начала изменим веса ребер так, чтобы они были равны <tex>\pm1</tex>. Заметим, что замена ребра веса <tex>k</tex> на <tex>k</tex> параллельных ребер веса <tex>1</tex> не меняет перманента матрицы. В графе не допускаются параллельные ребра, но мы можем сделать их допустимыми, если разобьем каждое из них на два, добавив новые вершины. Чтобы избавиться от ребер с отрицательным весом, заметим, что перманент графа <tex>G</tex> с весами ребер равными <tex>\pm1</tex> равен числу из отрезка <tex>[-n!, \, n!]</tex> и может быть вычислен как <tex>y = x \,  ( mod \, 2^{m+1})</tex>, где <tex>m</tex> достаточно большое (например, <tex>m = n^2</tex>. Для того, чтобы вычислить <tex>y</tex> достаточно посчитать перманент графа, где все ребра веса <tex>-1</tex> заменены на ребра веса <tex>2^m</tex>. Эти ребра могут быть заменены на <tex>m</tex> ребер весом <tex>2</tex>, которые можно разбить на двойки параллельных ребер весом <tex>+1</tex>, как на предыдущем шаге.
+Теперь сведем полученную матрицу к <tex>0,1-</tex>матрице. Для начала изменим веса ребер так, чтобы они были равны <tex>\pm1</tex>. Заметим, что замена ребра веса <tex>k</tex> на <tex>k</tex> параллельных ребер веса <tex>1</tex> не меняет перманента матрицы. В графе не допускаются параллельные ребра, но мы можем сделать их допустимыми, если разобьем каждое из них на два, добавив новые вершины. Чтобы избавиться от ребер с отрицательным весом, заметим, что перманент графа <tex>G</tex> с весами ребер равными <tex>\pm1</tex> равен числу из отрезка <tex>[-n!, \, n!]</tex> и может быть вычислен как <tex>y = x \,  ( mod \, 2^{m+1})</tex>, где <tex>m</tex> достаточно большое (например, <tex>m = n^2</tex>. Для того, чтобы вычислить <tex>y</tex>, достаточно посчитать перманент матрицы смежности графа, где все ребра веса <tex>-1</tex> заменены на ребра веса <tex>2^m</tex>. Эти ребра могут быть заменены на <tex>m</tex> ребер весом <tex>2</tex>, которые можно разбить на двойки параллельных ребер весом <tex>+1</tex>, как на предыдущем шаге.
 Таким образом для данной нам формулы мы за полиномиальное время построили соответствующий граф <tex>G'</tex> такой, что <tex>perm(A') = 4^m\cdot(\#\phi)</tex>, где <tex>A'</tex> - матрица смежности графа <tex>G'</tex> и свели задачу <tex>\#3SAT</tex> к задаче <tex>perm</tex>. Значит задача <tex>perm</tex> является <tex>\#P</tex>-полной.