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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Замечание)
(не показано 36 промежуточных версий 4 участников)
Строка 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>\#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>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.
+
По аналогии с классом <tex>NP</tex> мы можем дать альтернативное определение определение классу <tex>\#P</tex>, используя понятие недетерменированной МТ.
 +
{{Определение
 +
|definition = '''Класс''' <tex>\#P-</tex>  класс задач подсчета, решением которых является количество успешных (завершающихся в допускающих состояниях) путей вычислений для '''недетерминированной''' МТ, работающей за полиномиальное время. Отличается от большинства рассмотренных классов тем, что задачи требуют в качестве ответа не  <tex>``0"</tex> или <tex>``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\}^* </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.
 
*Для данного массива целых чисел посчитать количество подмножеств его элементов, таких, что сумма по всем элементам подмножества равняется 0.
Строка 17: Строка 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==
 
==Класс #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>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> 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 - \#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>.
 
Если <tex>f \in FP </tex>, тогда <tex>FP=FP^f</tex>. Получаем, что, если <tex>f -  \#P</tex>-полная и  <tex>f \in FP</tex>, то <tex>FP=\#P</tex>.
  
Для множества языков из <tex>NP</tex> (таких как <tex>3SAT, CLIQUE, Ham </tex>) существуют их версии из <tex>\#P</tex>. См. <tex>\#SAT</tex>.
+
== Примеры #P-Complete задач ==
 
 
== Примеры #P-полных задач ==
 
Многие задачи из класса <tex>\#P-</tex>полных получаются из задач разрешимости из класса <tex>P</tex>  за счет требования подсчета всевозможных удовлетворяющих наборов входных значений.
 
 
*[[#SAT]]
 
*[[#SAT]]
*Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.  
+
*Посчитать количество удовлетворяющих назначений для заданной в ДНФ формулы.  
 
*Посчитать количество полных паросочетаний в данном двудольном графе.  
 
*Посчитать количество полных паросочетаний в данном двудольном графе.  
 
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
 
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
Строка 49: Строка 54:
  
 
{{Определение
 
{{Определение
  |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> множество всех перестановок из n элементов.  
+
  |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> элементов.  
 
}}
 
}}
  
Строка 56: Строка 61:
 
Задача вычисления перманента матрицы, заполненной нулями и единицами является <tex>\#P-</tex>полной.
 
Задача вычисления перманента матрицы, заполненной нулями и единицами является <tex>\#P-</tex>полной.
 
|proof=
 
|proof=
Далее будем рассматривать матрицу <tex>A'</tex> как матрицу смежности двудольного графа <tex>G'</tex> : <tex>X = \{x_1, …, x_n\}, \, Y = \{y_1, …, y_n\}, \,  \{x_i, y_j\} \in V(G) \iff A_{i, j} = 1</tex>. Назовем покрытие ориентированного графа циклами такой подграф, что для любой вершины есть  ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда <tex>perm(A)</tex> равен сумме весов всех возможных покрытий циклами.
+
[[Файл: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>\#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>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>\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>.  
  
Построим граф <tex>G'</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>G'</tex> выполним за полиномиальное время. Для этого будем использовать три вида блоков. (Все ребра, для которых на схеме не указан вес, имеют вес <tex>1</tex>.)
  
'''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению true или false данной переменной. Присвоение true соответствует покрытию, содержащему все "внешние" ребра, присвоение false соответствует циклу, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
+
'''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению <tex>true</tex> или <tex>false</tex> данной переменной. Присвоение <tex>true</tex> соответствует покрытию, содержащему все "внешние" ребра, присвоение <tex>false</tex> соответствует покрытию, включающему ребра-петли и ребро <tex>``false"</tex>. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
  
'''Блок клоза'''. Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует покрытие веса 1. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменной, присутствующей в нем.
+
'''Блок клоза'''. Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует единственное покрытие и его вес равен <tex>1</tex>. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменной, присутствующей в нем.
  
'''Блок <tex>XOR</tex>'''. Цель данного клоза - убедиться, что для произвольной пары ребер <tex>uu'</tex> и <tex>vv'</tex> ровно одно из них присутствует в любом из покрытий циклами, учитывающие в итоговой сумме. Допустим, мы заменяем пару ребер <tex>uu'</tex> и <tex>vv'</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> и при дальнейшем подсчете мы можем их не учитывать. Блок <tex>XOR</tex>'a соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям.  
+
'''Блок 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 соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям нашей формулы.  
  
Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи <tex>XOR</tex>-блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменной, что аналогично присвоению переменной значения true. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначению. А для каждого удовлетворяющего назначения существует множество циклов суммарным весом <tex>4^{3m}</tex>, так как они проходят через блоки <tex>XOR</tex> ровно <tex>3m</tex> раз. Таким образом <tex>perm(G') = 4^{3m}\#\phi</tex>.
+
Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи XOR-блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменной, что аналогично присвоению переменной значения <tex>true</tex>. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначению формулы в 3-КНФ. А для каждого удовлетворяющего назначения существует множество циклов суммарным весом <tex>4^{3m}</tex>, так как они проходят через блоки XOR ровно <tex>3m</tex> раз. Таким образом <tex>perm(G') = 4^{3m}\cdot\#\phi</tex>.
  
Теперь сведем полученную матрицу к 0,1-матрице. Для начала изменим веса ребер так, чтобы были равны <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>полной.
 
}}
 
}}
  
 
===Замечание===
 
===Замечание===
  
Задача вычисления перманента матрицы, элементы которой принадлежат множеству <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>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]полной.

Источники


См. также