Изменения
→Примеры #P-полных задач
По данной формуле <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>.
Основная идея заключается в том, что наше построение будет приводить к существованию в соответствующем двудольном графе <tex>G'</tex> циклов двух видов: тех, которые соответствуют удовлетворяющим назначениям, и тех, которые не соответствуют. Покажем, что любое удовлетворяющее назначение добавляет <tex>4^m</tex> к <tex>perm(A')</tex>.
Тогда <tex>perm(A')=4^m\cdot(\#\phi)</tex>. Для построения графа <tex>G'</tex> будем использовать три вида блоков.
'''Блок переменной'''. Блок каждой переменной имеет два цикла положительного веса, соответствующие присвоению 0 и 1 данной переменной. Присвоение 1 соответствует циклу, содержащему все "внешние" ребра, присвоение 0 соответствует циклу, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
'''Блок клоза'''. Любой цикл для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует цикл веса 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.
}}
