Классы Sharp P, Sharp P-Complete — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры задач из #P)
(не показано 47 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
== Класс #P ==
 
== Класс #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>.
+
}}
 +
По аналогии с классом <tex>NP</tex> мы можем дать альтернативное определение определение классу <tex>\#P</tex>, используя понятие недетерменированной МТ.
 +
{{Определение
 +
|definition = '''Класс''' <tex>\#P-</tex>  класс задач подсчета, решением которых является количество успешных (завершающихся в допускающих состояниях) путей вычислений для '''недетерминированной''' МТ, работающей за полиномиальное время. Отличается от большинства рассмотренных классов тем, что задачи требуют в качестве ответа не  <tex>``0"</tex> или <tex>``1"</tex>, а натуральное число.
 
}}
 
}}
Вопрос, являются ли задачи из <tex>\#P</tex> //эффективно разрешимыми// остается открытым. Класс <tex>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>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.
+
 
 +
{{Определение
 +
|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\}^* </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>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.
  
 
== Примеры задач из #P ==
 
== Примеры задач из #P ==
*[[#SAT]]
+
*[[Sharp SAT|#SAT]]
* <tex>\#CYCLE</tex> - имея ориентированный граф <tex>G</tex>, посчитать число простых циклов. Аналогичная задача, отвечающая на вопрос, существует ли в заданном ориентированном графе простой цикл, может быть решена за линейное время при помощи поиска в ширину. Проблема подсчета значительно сложнее.
+
* <tex>\#CYCLE</tex> - имея ориентированный граф <tex>G</tex>, посчитать число простых циклов. Аналогичная задача, отвечающая на вопрос, существует ли в заданном ориентированном графе простой цикл, может быть решена за линейное время при помощи поиска в ширину. Проблема подсчета всех простых циклов значительно сложнее.
 +
*Для данного массива целых чисел посчитать количество подмножеств его элементов, таких, что сумма по всем элементам подмножества равняется 0.
 +
*Для данного взвешенного неориентированного графа посчитать количество Гамильтоновых циклов веса меньше k.
  
 
{{Теорема
 
{{Теорема
Строка 15: Строка 25:
  
 
|proof=
 
|proof=
[[Файл:dir_grap.png|thumb|300px| <tex>deg^{-}+deg^{+}=10=2\cdot |E|</tex>]]
+
[[Файл:cycle_block.png|thumb|300px|Блок H]]
Для графа <tex>G</tex> с n вершинами построим граф <tex>G'</tex> такой, что в <tex>G</tex> есть Гамильтонов цикл тогда и только тогда, когда в <tex>G'</tex> есть <tex>n^{n^2}</tex> циклов. Чтобы получить <tex>G'</tex>, заменим каждое ребро <tex>(u,v)</tex> из <tex>G</tex> на блок <tex>H</tex>.  Блок состоит из <tex>m = n * \log{n} + 1</tex> уровней. <tex>G</tex> представляет из себя ацикличный граф, а значит циклы в <tex>G'</tex> соответствуют циклам в <tex>G</tex>. Кроме того, существует <tex>2^m</tex> различных путей между <tex>u</tex> и <tex>v</tex> внутри блока, следовательно простому циклу длины <tex>l</tex> в <tex>G</tex> соответствует цикл длины <tex>2^{(ml)}</tex> в <tex>G'</tex>.  
+
Для графа <tex>G</tex> с <tex>n</tex> вершинами построим граф <tex>G'</tex> такой, что в <tex>G</tex> есть Гамильтонов цикл тогда и только тогда, когда в <tex>G'</tex> есть <tex>n^{n^2}</tex> циклов. Чтобы получить <tex>G'</tex>, заменим каждое ребро <tex>(u,v)</tex> из <tex>G</tex> на блок <tex>H</tex>.  Блок состоит из <tex>m = n \cdot \log{n} + 1</tex> уровней. <tex>H</tex> представляет из себя ацикличный граф, а значит циклы в <tex>G'</tex> соответствуют циклам в <tex>G</tex>. Кроме того, существует <tex>2^m</tex> различных путей между <tex>u</tex> и <tex>v</tex> внутри блока, следовательно простому циклу длины <tex>l</tex> в <tex>G</tex> соответствует цикл длины <tex>2^{(ml)}</tex> в <tex>G'</tex>.  
 
<br>
 
<br>
Заметим, что если граф <tex>G</tex> содержит гамильтонов цикл, то в <tex>G'</tex> существует минимум <tex>2^{m(n-1)} > n^{n^2}</tex> циклов.
+
Заметим, что, если граф <tex>G</tex> содержит гамильтонов цикл, то в <tex>G'</tex> существует минимум <tex>2^{mn} > n^{n^2}</tex> циклов.
 
<br>
 
<br>
Проверим в обратную сторону. Если в <tex>G</tex> не существует Гамильтонова цикла, то самый длинный цикл в <tex>G</tex> имеет длину не больше <tex>n-1</tex> и число циклов не может превысить <tex>n^{n-1}</tex>. Таким образом, в <tex>G'</tex> будет не более чем <tex>(2^m)^{n-1} * n^{n-1} < n^{n^2}</tex> циклов.му входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа чётна и равна удвоенному числу рёбер.
+
Проверим в обратную сторону. Если в <tex>G</tex> не существует Гамильтонова цикла, то самый длинный цикл в <tex>G</tex> имеет длину не больше <tex>n-1</tex> и число циклов не может превысить <tex>n^{n-1}</tex>. Таким образом, в <tex>G'</tex> будет не более чем <tex>(2^m)^{n-1} \cdot n^{n-1} < n^{n^2}</tex> циклов.
 
<br>
 
<br>
Преобразование графа <tex>G</tex> в <tex>G'</tex> можно выполнить за полином от количества вершин. Таким образом, если <tex>\#CYCLE \in FP</tex>, тогда сразу же <tex>HAM \in P</tex>. А так как<tex> HAM \in NP</tex>, то <tex>NP = P</tex>.
+
Преобразование графа <tex>G</tex> в <tex>G'</tex> можно выполнить за полином от количества вершин. Таким образом, если <tex>\#CYCLE \in FP</tex>, тогда сразу же <tex>HAM \in P</tex>. А так как <tex>HAM \in NP</tex>, то <tex>NP = P</tex>.
 +
}}
 +
 
 +
==Класс #P-Complete==
 +
{{Определение
 +
|definition= <tex>f : \{0, 1\}^* \rightarrow  \{0, 1\}^*</tex> является <tex>\#P</tex>-полной, если <tex> f  \in \#P</tex> и любая проблема из <tex>\#P</tex> может быть сведена к ней за полиномиальное время.
 
}}
 
}}
  
 +
Будем использовать МТ с оракулом <tex> O = \{\big \langle x, i \big \rangle: f(x)_i = 1\}</tex> для нашей функции <tex>f</tex>. Для нашего типа задач оракул будет отвечать на вопросы вида "Принадлежит ли слово <tex>q</tex> языку <tex>O</tex>?" за один шаг МТ. Для функции <tex>f = \{0,1\}^* \rightarrow  \{0, 1\}^*</tex> будем называть <tex>FP^f</tex> множество функций, вычислимых за полиномиальное время на МТ с оракулом для функции <tex>f</tex>.
 +
 +
Тогда <tex>f - \#P-</tex>полная, если <tex>f \in \#P</tex> и  любая <tex>g \in \#P</tex> принадлежит <tex>FP^f</tex>.
 +
 +
Если <tex>f \in FP </tex>, тогда <tex>FP=FP^f</tex>. Получаем, что, если <tex>f -  \#P</tex>-полная и  <tex>f \in FP</tex>, то <tex>FP=\#P</tex>.
 +
 +
== Примеры #P-Complete задач ==
 +
*[[#SAT]]
 +
*Посчитать количество удовлетворяющих назначений для заданной в ДНФ формулы.
 +
*Посчитать количество полных паросочетаний в данном двудольном графе.
 +
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
 +
*Вычислить значение перманента матрицы, заполненной нулями и единицами.
  
==Класс #P-Complete==
 
 
{{Определение
 
{{Определение
|definition= <tex>f : \{0, 1\}^* \rightarrow  \{0, 1\}^*</tex> является <tex>\#P</tex>-полной, если <tex> f  \in \#P</tex> и получение для <tex>f</tex> алгоритма работающего за полиномиальное время влечет равенство <tex> \#P=FP</tex>.
+
|definition =Перманентом матрицы А размером <tex>n \times n</tex> называется <tex>perm(A) = \sum\limits_{\sigma \in S_n} \prod\limits^n_{i =1}A_{i\sigma(i)}</tex>, где <tex>S_n -</tex> множество всех перестановок из <tex>n</tex> элементов.  
 
}}
 
}}
  
Для более формального определения будем использовать МТ с оракулом <tex> О = \{\big \langle x, i \big \rangle: f(x)_i = 1\}</tex>. Для нашего типа задач оракул будет отвечать на вопросы вида
+
{{Теорема
 +
|statement=
 +
Задача вычисления перманента матрицы, заполненной нулями и единицами является <tex>\#P-</tex>полной.
 +
|proof=
 +
[[Файл:Variable_block.png|thumb|200px|Блок переменной]]
 +
[[Файл:clause_block.png|thumb|150px|Блок клоза]]
 +
[[Файл:xor_block.png|thumb|200px|Блок XOR]]
 +
[[Файл:blocks_connection.png|thumb|200px|Блок XOR]]
 +
Задача нахождения перманента <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>.
 +
 
 +
По данной формуле <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>.
 +
 
 +
Построение графа <tex>G'</tex> выполним за полиномиальное время. Для этого будем использовать три вида блоков. (Все ребра, для которых на схеме не указан вес, имеют вес <tex>1</tex>.)
 +
 
 +
'''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению <tex>true</tex> или <tex>false</tex> данной переменной. Присвоение <tex>true</tex> соответствует покрытию, содержащему все "внешние" ребра, присвоение <tex>false</tex> соответствует покрытию, включающему ребра-петли и ребро <tex>``false"</tex>. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
 +
 
 +
'''Блок клоза'''. Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует  единственное покрытие и его вес равен <tex>1</tex>. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменной, присутствующей в нем.
 +
 
 +
'''Блок XOR'''. Цель данного блока - убедиться, что для произвольной пары ребер <tex>uu'</tex> и <tex>vv'</tex> ровно одно из них присутствует в любом из покрытий циклами, учитывающемся в итоговой сумме.  Представим, что мы заменяем пару ребер <tex>uu'</tex> и <tex>vv'</tex> в некотором графе <tex>G</tex> на блок XOR. Каждый цикл в <tex>G</tex> веса <tex>w</tex>, проходящий через ровно одно из ребер <tex>uu'</tex> и <tex>vv'</tex>, превращается в набор циклов в графе <tex>G'</tex> общим весом <tex>4w</tex>: вклад дает набор циклов, которые заходят в блок через <tex>u</tex> и выходят через <tex>u'</tex> или заходят через <tex>v</tex> и выходят через <tex>v'</tex>, вес остальных циклов в сумме равняется <tex>0</tex> и при дальнейшем подсчете мы можем их не учитывать. Блок XOR'a соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям нашей формулы.
 +
 
 +
Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи 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>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>\{0,1\}</tex> может быть сведена к задаче подсчета числа совершенных паросочетаний в двудольном графе <tex>G</tex>. Тогда <tex>\prod\limits^n_{i =1}A_{i\sigma(i)} = 1</tex> тогда и только тогда, когда <tex>\sigma</tex> является совершенным паросочетанием. В таком случае, <tex>perm(A)</tex> равен числу совершенных паросочетаний в графе <tex>G</tex>. А значит задача подсчета числа совершенных паросочетаний в двудольном графе эквивалентна задаче вычисления перманента <tex>\{0,1\}-</tex>матрицы и также является <tex>\#P-</tex>полной.
 +
 
 +
==Источники==
 +
*[http://theory.cs.princeton.edu/complexity/book.pdf Christos H. Papadimitriou. Computational Complexity. c. 172-179]
 +
*[https://en.wikipedia.org/wiki/Counting_problem_(complexity) Counting problem]
 +
*[https://en.wikipedia.org/wiki/Sharp-P Sharp-P ]
 +
*[https://en.wikipedia.org/wiki/Sharp-P-complete Sharp-P-complete]
 +
*[https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent Sharp-P-completeness of 01-permanent]
 +
*[https://shaih.github.io/pubs/01perm.pdf Zero One Permanent is  #P-Complete,  A Simpler Proof]
 +
 
 +
 
 +
== См. также ==
 +
*[[Класс P]]
 +
*[[Классы NP, coNP, Σ₁, Π₁]]
 +
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 +
 
 +
[[Категория:Классы сложности]]

Версия 16:05, 14 ноября 2018

Класс #P

Определение:
[math]f : \{0,1\}^* \rightarrow \mathbb{N}[/math] принадлежит [math]\#P[/math], если существует [math]p \in Poly[/math] и работающая за полиномиальное время машина Тьюринга [math]M[/math] такая, что для любого [math]x \in \{0,1\}^* : f(x) = | \{y \in \{0,1\}^{p(|x|)} : M(x,y) = 1 \} |[/math].

По аналогии с классом [math]NP[/math] мы можем дать альтернативное определение определение классу [math]\#P[/math], используя понятие недетерменированной МТ.

Определение:
Класс [math]\#P-[/math] класс задач подсчета, решением которых является количество успешных (завершающихся в допускающих состояниях) путей вычислений для недетерминированной МТ, работающей за полиномиальное время. Отличается от большинства рассмотренных классов тем, что задачи требуют в качестве ответа не [math]``0"[/math] или [math]``1"[/math], а натуральное число.


Определение:
Класс [math]\mathrm{FP}[/math] — класс задач подсчета, разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть: [math]f : \{0,1\}^* \rightarrow \mathbb{N}[/math] принадлежит [math]FP[/math], если существует [math]p \in Poly[/math] и работающая за полиномиальное время детерминированная машина Тьюринга [math]M[/math] такая, что для любого [math]x \in \{0,1\}^* [/math] выполняется [math] f(x) = M(x)[/math].

Вопрос, являются ли задачи из [math]\#P[/math] эффективно разрешимыми, остается открытым. Подсчет числа сертификатов как минимум столь же сложен, как и проверка наличия сертификата, а значит, если, доказать равенство [math]\#P=FP[/math], то автоматически будет доказано [math]NP=P[/math]. Однако, из [math]NP=P[/math] вовсе не следует [math]\#P=FP[/math]. Также можно заметить, что если [math]PSPACE = P[/math], то [math]\#P=FP[/math], так как подсчет числа сертификатов может быть выполнен за полиномиальную память.

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

  • #SAT
  • [math]\#CYCLE[/math] - имея ориентированный граф [math]G[/math], посчитать число простых циклов. Аналогичная задача, отвечающая на вопрос, существует ли в заданном ориентированном графе простой цикл, может быть решена за линейное время при помощи поиска в ширину. Проблема подсчета всех простых циклов значительно сложнее.
  • Для данного массива целых чисел посчитать количество подмножеств его элементов, таких, что сумма по всем элементам подмножества равняется 0.
  • Для данного взвешенного неориентированного графа посчитать количество Гамильтоновых циклов веса меньше k.
Теорема:
Если [math]\#CYCLE \in FP[/math], тогда [math]P=NP[/math].
Доказательство:
[math]\triangleright[/math]
Блок H

Для графа [math]G[/math] с [math]n[/math] вершинами построим граф [math]G'[/math] такой, что в [math]G[/math] есть Гамильтонов цикл тогда и только тогда, когда в [math]G'[/math] есть [math]n^{n^2}[/math] циклов. Чтобы получить [math]G'[/math], заменим каждое ребро [math](u,v)[/math] из [math]G[/math] на блок [math]H[/math]. Блок состоит из [math]m = n \cdot \log{n} + 1[/math] уровней. [math]H[/math] представляет из себя ацикличный граф, а значит циклы в [math]G'[/math] соответствуют циклам в [math]G[/math]. Кроме того, существует [math]2^m[/math] различных путей между [math]u[/math] и [math]v[/math] внутри блока, следовательно простому циклу длины [math]l[/math] в [math]G[/math] соответствует цикл длины [math]2^{(ml)}[/math] в [math]G'[/math].
Заметим, что, если граф [math]G[/math] содержит гамильтонов цикл, то в [math]G'[/math] существует минимум [math]2^{mn} \gt n^{n^2}[/math] циклов.
Проверим в обратную сторону. Если в [math]G[/math] не существует Гамильтонова цикла, то самый длинный цикл в [math]G[/math] имеет длину не больше [math]n-1[/math] и число циклов не может превысить [math]n^{n-1}[/math]. Таким образом, в [math]G'[/math] будет не более чем [math](2^m)^{n-1} \cdot n^{n-1} \lt n^{n^2}[/math] циклов.

Преобразование графа [math]G[/math] в [math]G'[/math] можно выполнить за полином от количества вершин. Таким образом, если [math]\#CYCLE \in FP[/math], тогда сразу же [math]HAM \in P[/math]. А так как [math]HAM \in NP[/math], то [math]NP = P[/math].
[math]\triangleleft[/math]

Класс #P-Complete

Определение:
[math]f : \{0, 1\}^* \rightarrow \{0, 1\}^*[/math] является [math]\#P[/math]-полной, если [math] f \in \#P[/math] и любая проблема из [math]\#P[/math] может быть сведена к ней за полиномиальное время.


Будем использовать МТ с оракулом [math] O = \{\big \langle x, i \big \rangle: f(x)_i = 1\}[/math] для нашей функции [math]f[/math]. Для нашего типа задач оракул будет отвечать на вопросы вида "Принадлежит ли слово [math]q[/math] языку [math]O[/math]?" за один шаг МТ. Для функции [math]f = \{0,1\}^* \rightarrow \{0, 1\}^*[/math] будем называть [math]FP^f[/math] множество функций, вычислимых за полиномиальное время на МТ с оракулом для функции [math]f[/math].

Тогда [math]f - \#P-[/math]полная, если [math]f \in \#P[/math] и любая [math]g \in \#P[/math] принадлежит [math]FP^f[/math].

Если [math]f \in FP [/math], тогда [math]FP=FP^f[/math]. Получаем, что, если [math]f - \#P[/math]-полная и [math]f \in FP[/math], то [math]FP=\#P[/math].

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

  • #SAT
  • Посчитать количество удовлетворяющих назначений для заданной в ДНФ формулы.
  • Посчитать количество полных паросочетаний в данном двудольном графе.
  • Посчитать количество способов раскрасить заданный граф в [math]k[/math] цветов.
  • Вычислить значение перманента матрицы, заполненной нулями и единицами.


Определение:
Перманентом матрицы А размером [math]n \times n[/math] называется [math]perm(A) = \sum\limits_{\sigma \in S_n} \prod\limits^n_{i =1}A_{i\sigma(i)}[/math], где [math]S_n -[/math] множество всех перестановок из [math]n[/math] элементов.


Теорема:
Задача вычисления перманента матрицы, заполненной нулями и единицами является [math]\#P-[/math]полной.
Доказательство:
[math]\triangleright[/math]
Блок переменной
Блок клоза
Блок XOR
Блок XOR

Задача нахождения перманента [math]0,1-[/math]матрицы может быть сформулирована как задача подсчета количества перестановок, для которых произведение соответствующих элементов матрицы равно [math]1[/math]. В такой формулировке задача нахождения перманента [math]0,1-[/math]матрицы принадлежит классу [math]\#P[/math] по определению.

Докажем, что задача [math]perm[/math] является [math]\#P-[/math]полной. Нам известно, что задача [math]\#SAT[/math] является [math]\#P-[/math]полной. Аналогично задачам [math]SAT[/math] и [math]3SAT[/math] мы можем сказать, что задача [math]\#SAT[/math] может быть сведена к задаче [math]\#3SAT[/math], которая также будет [math]\#P-[/math]полной. Теперь сведем задачу [math]\#3SAT[/math] к задаче [math]perm[/math].

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

Для этого по данной 3-КНФ формуле построим ориентированный граф [math]G'[/math] таким образом, чтобы в нем существовали покрытия циклами двух видов: те, которые соответствуют удовлетворяющим назначениям, и те, которые не соответствуют. Назовем покрытием ориентированного графа циклами такой подграф, что для любой вершины есть ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда [math]perm(A)[/math] равен сумме весов всех возможных покрытий циклами. Далее покажем, что любое удовлетворяющее назначение для формулы [math]\phi[/math] будет добавлять [math]4^m[/math] к [math]perm(A')[/math], а любое другое назначение не будет вносить вклад. Тогда [math]perm(A')=4^m\cdot(\#\phi)[/math].

Построение графа [math]G'[/math] выполним за полиномиальное время. Для этого будем использовать три вида блоков. (Все ребра, для которых на схеме не указан вес, имеют вес [math]1[/math].)

Блок переменной. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению [math]true[/math] или [math]false[/math] данной переменной. Присвоение [math]true[/math] соответствует покрытию, содержащему все "внешние" ребра, присвоение [math]false[/math] соответствует покрытию, включающему ребра-петли и ребро [math]``false"[/math]. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.

Блок клоза. Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует единственное покрытие и его вес равен [math]1[/math]. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменной, присутствующей в нем.

Блок XOR. Цель данного блока - убедиться, что для произвольной пары ребер [math]uu'[/math] и [math]vv'[/math] ровно одно из них присутствует в любом из покрытий циклами, учитывающемся в итоговой сумме. Представим, что мы заменяем пару ребер [math]uu'[/math] и [math]vv'[/math] в некотором графе [math]G[/math] на блок XOR. Каждый цикл в [math]G[/math] веса [math]w[/math], проходящий через ровно одно из ребер [math]uu'[/math] и [math]vv'[/math], превращается в набор циклов в графе [math]G'[/math] общим весом [math]4w[/math]: вклад дает набор циклов, которые заходят в блок через [math]u[/math] и выходят через [math]u'[/math] или заходят через [math]v[/math] и выходят через [math]v'[/math], вес остальных циклов в сумме равняется [math]0[/math] и при дальнейшем подсчете мы можем их не учитывать. Блок XOR'a соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям нашей формулы.

Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи XOR-блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменной, что аналогично присвоению переменной значения [math]true[/math]. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначению формулы в 3-КНФ. А для каждого удовлетворяющего назначения существует множество циклов суммарным весом [math]4^{3m}[/math], так как они проходят через блоки XOR ровно [math]3m[/math] раз. Таким образом [math]perm(G') = 4^{3m}\cdot\#\phi[/math].

Теперь сведем полученную матрицу к [math]0,1-[/math]матрице. Для начала изменим веса ребер так, чтобы они были равны [math]\pm1[/math]. Заметим, что замена ребра веса [math]k[/math] на [math]k[/math] параллельных ребер веса [math]1[/math] не меняет перманента матрицы. В графе не допускаются параллельные ребра, но мы можем сделать их допустимыми, если разобьем каждое из них на два, добавив новые вершины. Чтобы избавиться от ребер с отрицательным весом, заметим, что перманент графа [math]G[/math] с весами ребер равными [math]\pm1[/math] равен числу из отрезка [math][-n!, \, n!][/math] и может быть вычислен как [math]y = x \, ( mod \, 2^{m+1})[/math], где [math]m[/math] достаточно большое (например, [math]m = n^2[/math]. Для того, чтобы вычислить [math]y[/math], достаточно посчитать перманент матрицы смежности графа, где все ребра веса [math]-1[/math] заменены на ребра веса [math]2^m[/math]. Эти ребра могут быть заменены на [math]m[/math] ребер весом [math]2[/math], которые можно разбить на двойки параллельных ребер весом [math]+1[/math], как на предыдущем шаге.

Таким образом для данной нам формулы мы за полиномиальное время построили соответствующий граф [math]G'[/math] такой, что [math]perm(A') = 4^m\cdot(\#\phi)[/math], где [math]A'[/math] - матрица смежности графа [math]G'[/math] и свели задачу [math]\#3SAT[/math] к задаче [math]perm[/math]. Значит задача [math]perm[/math] является [math]\#P-[/math]полной.
[math]\triangleleft[/math]

Замечание

Задача вычисления перманента матрицы, элементы которой принадлежат множеству [math]\{0,1\}[/math] может быть сведена к задаче подсчета числа совершенных паросочетаний в двудольном графе [math]G[/math]. Тогда [math]\prod\limits^n_{i =1}A_{i\sigma(i)} = 1[/math] тогда и только тогда, когда [math]\sigma[/math] является совершенным паросочетанием. В таком случае, [math]perm(A)[/math] равен числу совершенных паросочетаний в графе [math]G[/math]. А значит задача подсчета числа совершенных паросочетаний в двудольном графе эквивалентна задаче вычисления перманента [math]\{0,1\}-[/math]матрицы и также является [math]\#P-[/math]полной.

Источники


См. также