Изменения

|definition =<tex>\#P</tex> представляет класс задач, решением которых является количество успешных (завершающихся в допускающих состояниях) путей вычислений для недетерминированной МТ, работающей за полиномиальное время. Отличается от большинства рассмотренных классов тем, что задачи требуют в качестве ответа не <tex>``0"</tex> или <tex>``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>, а натуральное число.

Вопрос{{Определение |definition ='''Класс''' <tex>\mathrm{FP}</tex> {{---}} класс задач подсчета, разрешимых на '''детерминированной''' машине Тьюринга за полиномиальное время, являются ли задачи из то есть:<tex>f : \{0,1\}^* \#Prightarrow \mathbb{N}</tex> принадлежит <tex>FP</tex>, если существует <tex>p \in Poly</эффективно разрешимымиtex> и работающая за полиномиальное время '''детерминированная''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* </ остается открытым. Класс tex> выполняется <tex>FPf(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>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.

*[[Sharp SAT|#SAT]]

[[Файл:dir_grapcycle_block.png|thumb|300px| <tex>deg^{-}+deg^{+}=10=2\cdot |E|</tex>Блок H]]Для графа <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>GH</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>G'</tex> существует минимум <tex>2^{m(n-1)mn} > 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> циклов.му входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа чётна и равна удвоенному числу рёбер.

Преобразование графа <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>.

|definition= <tex>f : \{0, 1\}^* \rightarrow \{0, 1\}^*</tex> является <tex>\#P</tex>-полной, если <tex> f \in \#P</tex> и получение для любая проблема из <tex>f\#P</tex> алгоритма работающего может быть сведена к ней за полиномиальное время влечет равенство <tex> \#P=FP</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>NP</tex> (таких как <tex>3SAT, CLIQUE, Ham </tex>) существуют их версии из <tex>\#P</tex>. См. <tex>\#SAT</tex>. == Примеры #P-полных Complete задач ==Многие задачи из класса <tex>\#P-</tex>полных получаются из задач разрешимости из класса <tex>P</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> элементов.

Далее будем рассматривать матрицу [[Файл:Variable_block.png|thumb|200px|Блок переменной]][[Файл:clause_block.png|thumb|150px|Блок клоза]][[Файл:xor_block.png|thumb|200px|Блок XOR]][[Файл:blocks_connection.png|thumb|200px|Блок XOR]]Задача нахождения перманента <tex>A'0,1-</tex> матрицы может быть сформулирована как матрицу смежности двудольного графа задача подсчета количества перестановок, для которых произведение соответствующих элементов матрицы равно <tex>G'1</tex> : . В такой формулировке задача нахождения перманента <tex>X = \{x_1, …, x_n\}, \0, Y = \{y_1, …, y_n\}, \, \{x_i, y_j\} \in V(G) \iff A_{i, j} = 1-</tex>. Назовем покрытие ориентированного графа циклами такой подграф, что для любой вершины есть ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда матрицы принадлежит классу <tex>perm(A)\#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> выполним за полиномиальное время. Для этого будем использовать три вида блоков.[[Файл:Variable_block.png|thumb|250px|Блок переменной]]'''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению true или false данной переменной. Присвоение true соответствует покрытию, содержащему все "внешние" (Все ребра, присвоение false соответствует циклудля которых на схеме не указан вес, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменнаяимеют вес <tex>1</tex>.)

'''Блок клозапеременной'''. Любое покрытие Блок каждой переменной имеет два покрытия циклами для данного блока не содержит в себе как минимум одно внешнее , соответствующие присвоению <tex>true</tex> или <tex>false</tex> данной переменной. Присвоение <tex>true</tex> соответствует покрытию, содержащему все "внешние" ребра, присвоение <tex>false</tex> соответствует покрытию, включающему ребра-петли и ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует покрытие веса 1<tex>``false"</tex>. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменнойодним клозом, присутствующей в немкотором присутствует данная переменная.

'''Блок XORклоза'''. Цель Любое покрытие циклами для данного клоза - убедиться, что для произвольной пары ребер <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>01</tex> и при дальнейшем подсчете мы можем их не учитывать. Блок XOR'a соединяет блоки переменных Каждое внешнее ребро рассматриваемого клоза ассоциировано с соответствующими блоками клозов такодной переменной, чтобы вклад присутствующей в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям нашей формулынем.

Рассмотрим клоз и переменную внутри него'''Блок XOR'''. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи XORЦель данного блока -блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменнойубедиться, что аналогично присвоению переменной значения true. Так как хотя бы для произвольной пары ребер <tex>uu'</tex> и <tex>vv'</tex> ровно одно ребро из них присутствует в каждом блоке клоза будет пропущенолюбом из покрытий циклами, то каждый циклучитывающемся в итоговой сумме. Представим, который что мы учитываем соответствует удовлетворяющему назначению формулы заменяем пару ребер <tex>uu'</tex> и <tex>vv'</tex> в 3-КНФнекотором графе <tex>G</tex> на блок XOR. А для каждого удовлетворяющего назначения существует множество Каждый цикл в <tex>G</tex> веса <tex>w</tex>, проходящий через ровно одно из ребер <tex>uu'</tex> и <tex>vv'</tex>, превращается в набор циклов суммарным в графе <tex>G'</tex> общим весом <tex>4^{3m}4w</tex>: вклад дает набор циклов, так как они проходят которые заходят в блок через <tex>u</tex> и выходят через <tex>u'</tex> или заходят через блоки XOR ровно <tex>3mv</tex> раз. Таким образом и выходят через <tex>perm(Gv') = 4^{3m}\#\phi</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, Σ₁, Π₁]]*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]] [[Категория:Классы сложности]]