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> множество всех перестановок из n элементов.
}}
'''Блок клоза'''. Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует покрытие веса 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. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначениюформулы в 3-КНФ. А для каждого удовлетворяющего назначения существует множество циклов суммарным весом <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>, как на предыдущем шаге.
