41
правка
Изменения
→Примеры #P-полных задач
{{Определение
|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>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> равен сумме весов всех возможных покрытий циклами.
Очевидно, задача нахождения перманента 0,1-матрицы принадлежит классу <tex>\#P</tex>. Для вычисления будем недетерминированно выбирать перестановку из <tex>n</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>.
'''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению true или false данной переменной. Присвоение true соответствует покрытию, содержащему все "внешние" ребра, присвоение false соответствует циклу, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
'''Блок 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>0</tex> и при дальнейшем подсчете мы можем их не учитывать. Блок XOR'a соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям нашей формулы.
Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи XOR-блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменной, что аналогично присвоению переменной значения true. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначению формулы в 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>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>-полной.
}}
