Изменения

|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]]

[[Файл: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> за счет требования подсчета всевозможных удовлетворяющих наборов входных значений.

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

{{Определение[[Файл:Variable_block.png|thumb|200px|Блок переменной]][[Файл:clause_block.png|thumb|150px|Блок клоза]][[Файл:xor_block.png|thumb|200px|Блок XOR]] [[Файл:blocks_connection.png|thumb|definition =Перманентом 200px|Блок XOR]]Задача нахождения перманента <tex>0,1-</tex>матрицы А размером может быть сформулирована как задача подсчета количества перестановок, для которых произведение соответствующих элементов матрицы равно <tex>n \times n1</tex> называется. В такой формулировке задача нахождения перманента <tex>perm(A) = \sum\limits_{\sigma \in S_n} \prod\limits^n_{i =0,1}A_{i\sigma(i)}-</tex>, где матрицы принадлежит классу <tex>S_n -\#P</tex> множество всех перестановок из n элементовпо определению. }}

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

Тогда По данной формуле <tex>\prod\limitsphi</tex> с <tex>n</tex> переменными и <tex>m</tex> клозами построим целочисленную матрицу <tex>A'</tex> такую, что <tex>perm(A')=4^n_{i =1}A_{im\sigmacdot(i\#\phi)} = 1</tex> тогда и только тогда, когда где <tex>\sigma#\phi -</tex> количество удовлетворяющих подстановок для <tex>\phi</tex> является совершенным паросочетанием. В таком случае, Для этого будем рассматривать матрицу <tex>A'</tex> как матрицу смежности двудольного графа <tex>G'</tex> : <tex>permX = \{x_1 \ldots \, x_n\}, \, \{x_i, x_j\} \in V(AG)\iff A_{i, j} = 1</tex> равен числу совершенных паросочетаний в графе . Таким образом, нашей целью будет построение некоторого графа <tex>G'</tex>, матрицей смежности которого будет <tex>A'</tex>.

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

Сведем задачу Построение графа <tex>\#3SATG'</tex> к задаче выполним за полиномиальное время. Для этого будем использовать три вида блоков. (Все ребра, для которых на схеме не указан вес, имеют вес <tex>perm1</tex>.)

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

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

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

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