Изменения

|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\}^* \rightarrow \mathbb{N}</tex> принадлежит <tex>PFP</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>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.

*[[Sharp SAT|#SAT]]

[[Файл:Linecycle_block.jpgpng|thumb|300px|Блок XORH]]Для графа <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> за счет требования подсчета всевозможных удовлетворяющих наборов входных значений.

*Посчитать количество возможных подстановок, удовлетворяющих назначений для которых заданная заданной в ДНФ формула будет удовлетворенаформулы.

Далее будем рассматривать матрицу Задача нахождения перманента <tex>A'0,1-</tex> матрицы может быть сформулирована как матрицу смежности двудольного графа задача подсчета количества перестановок, для которых произведение соответствующих элементов матрицы равно <tex>G'1</tex> : . В такой формулировке задача нахождения перманента <tex>X = \{x_1, …, x_n\}, \, Y = \{y_1, …, y_n\}, \, \{x_i, y_j\} \in V(G) \iff A_{i0, j} = 1-</tex>. Назовем покрытие ориентированного графа циклами такой подграф, что для любой вершины есть ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда матрицы принадлежит классу <tex>perm(A)\#P</tex> равен сумме весов всех возможных покрытий цикламипо определению.

ОчевидноДокажем, что задача нахождения перманента 0<tex>perm</tex> является <tex>\#P-</tex>полной. Нам известно,1что задача <tex>\#SAT</tex> является <tex>\#P-матрицы принадлежит классу </tex>полной. Аналогично задачам <tex>SAT</tex> и <tex>3SAT</tex> мы можем сказать, что задача <tex>\#SAT</tex> может быть сведена к задаче <tex>\#3SAT</tex>, которая также будет <tex>\#P-</tex>полной. Для вычисления будем недетерминированно выбирать перестановку из Теперь сведем задачу <tex>n\#3SAT</tex> к задаче <tex>perm</tex> элементов и для каждой из них вычислять нужное значение за полиномиальное время.

Докажем, что задача По данной формуле <tex>\phi</tex> с <tex>permn</tex> является переменными и <tex>\#Pm</tex>-полной. Нам известно, что задача клозами построим целочисленную матрицу <tex>\#SATA'</tex> является такую, что <tex>perm(A')=4^m\cdot(\#P\phi)</tex>-полной. Аналогично задачам , где <tex>SAT\#\phi -</tex> и количество удовлетворяющих подстановок для <tex>3SAT\phi</tex> мы можем сказать, что задача . Для этого будем рассматривать матрицу <tex>\#SATA'</tex> может быть сведена к задаче как матрицу смежности двудольного графа <tex>\#3SATG'</tex>, которая также будет : <tex>X = \{x_1 \ldots \, x_n\}, \, \{x_i, x_j\} \in V(G) \#Piff A_{i, j} = 1</tex>-полной. Теперь сведем задачу Таким образом, нашей целью будет построение некоторого графа <tex>\#3SATG'</tex> к задаче , матрицей смежности которого будет <tex>permA'</tex>.

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

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

Построение графа '''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению <tex>G'true</tex> или <tex>false</tex> данной переменной. Присвоение <tex>true</tex> соответствует покрытию, содержащему все "внешние" ребра, присвоение <tex>false</tex> соответствует покрытию, включающему ребра-петли и ребро <tex>``false"</tex> выполним за полиномиальное время. Для этого будем использовать три вида блоковКаждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.

'''Блок переменнойклоза'''. Блок каждой переменной имеет два покрытия Любое покрытие циклами, соответствующие присвоению true или false данной переменнойдля данного блока не содержит в себе как минимум одно внешнее ребро. Присвоение true соответствует покрытию, содержащему все "внешние" ребра, присвоение false соответствует циклу, включающему ребра-петлиИ для любого подмножества внешних ребер (за исключением набора из всех ребер) существует единственное покрытие и его вес равен <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>, проходящий через ровно одно из всех ребер) существует покрытие веса 1<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>uu'true</tex> и <tex>vv'</tex> ровно . Так как хотя бы одно из них присутствует ребро в любом из покрытий цикламикаждом блоке клоза будет пропущено, учитывающемся в итоговой сумме. Допустимто каждый цикл, который мы заменяем пару ребер <tex>uu'</tex> и <tex>vv'</tex> на блок XORучитываем соответствует удовлетворяющему назначению формулы в 3-КНФ. Каждый цикл в <tex>G</tex> веса А для каждого удовлетворяющего назначения существует множество циклов суммарным весом <tex>w4^{3m}</tex>, проходящий так как они проходят через блоки XOR ровно одно из ребер <tex>uu'3m</tex> и <tex>vv'</tex>, превращается в набор циклов в графе раз. Таким образом <tex>perm(G') = 4^{3m}\cdot\#\phi</tex> общим весом <tex>4w</tex>: вклад дает набор циклов, которые заходят в блок через <tex>u</tex> и выходят через <tex>u'</tex> или заходят через <tex>v</tex> и выходят через <tex>v'</tex>, вес остальных циклов в сумме равняется <tex>0</tex> и при дальнейшем подсчете мы можем их не учитывать. Блок XOR'a соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям нашей формулы.

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