41
правка
Изменения
→Примеры #P-полных задач
Задача вычисления перманента матрицы, заполненной нулями и единицами является <tex>\#P-</tex>полной.
|proof=
[[Файл:Variable_block.png|thumb|200px|Блок переменной]]
[[Файл:clause_block.png|thumb|150px|Блок клоза]]
[[Файл:xor_block.png|thumb|200px|Блок XOR]]
[[Файл:blocks_connection.png|thumb|200px|Блок XOR]]
Далее будем рассматривать матрицу <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> равен сумме весов всех возможных покрытий циклами.
Для построения графа <tex>G'</tex> будем использовать три вида блоков.
'''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению true или false данной переменной. Присвоение true соответствует покрытию, содержащему все "внешние" ребра, присвоение false соответствует циклу, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
