41
правка
Изменения
→Примеры #P-полных задач
*Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.
*Посчитать количество полных паросочетаний в данном двудольном графе.
*Посчитать количество способов раскрасить заданный граф в <tex>k</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> множество всех перестановок из n элементов.
}}
{{Теорема
|statement=
Задача вычисления перманента матрицы, заполненной нулями и единицами является <tex>\#P-</tex>полной.
|proof=
'''Блок переменной'''. Блок каждой переменной имеет два цикла положительного весапокрытия циклами, соответствующие присвоению 0 и 1 true или false данной переменной. Присвоение 1 true соответствует циклупокрытию, содержащему все "внешние" ребра, присвоение 0 false соответствует циклу, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
'''Блок клоза'''. Любой цикл Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует цикл покрытие веса 1. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменной, присутствующей в рассматриваемом клозенем.
'''Блок <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 соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям.
Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи <tex>XOR</tex>-блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменной, что аналогично присвоению переменной значения true. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначению. А для каждого удовлетворяющего назначения существует множество циклов суммарным весом <tex>4^{3m}</tex>, так как они проходят через блоки <tex>XOR</tex> ровно <tex>3m</tex> раз. Таким образом <tex>perm(G') = 4^{3m}\#\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>G</tex>.
Тогда <tex>\prod\limits^n_{i =1}A_{i\sigma(i)} = 1</tex> тогда и только тогда, когда <tex>\sigma</tex> является совершенным паросочетанием. В таком случае, <tex>perm(A)</tex> равен числу совершенных паросочетаний в графе <tex>G</tex>.
