Изменения
→Примеры #P-полных задач
Многие задачи из класса <tex>\#P-</tex>полных получаются из задач разрешимости из класса <tex>P</tex> за счет требования подсчета всевозможных удовлетворяющих наборов входных значений.
*[[#SAT]]
* Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.
*Посчитать количество полных паросочетаний в данном двудольном графе.
*Вычислить значение перманента матрицы, заполненной нулями и единицами.
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
{{Теорема
|statement=
Задача вычисления перманента матрицы, заполненной нулями и единицами является <tex>\#P-</tex>полной.
|proof=
{{Определение
|definition =Перманентом матрицы А размером <tex>n x n</tex> называется <tex>perm(a) = \sum </tex>, где <tex>S_n -</tex> множество всех перестановок из n элементов.
}}
Задача вычисления перманента матрицы, элементы которой принадлежат множеству <tex>\{0,1\}</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>\prod^n_{i =1}A_{i\sigma(i)} = 1</tex> тогда и только тогда, когда <tex>\sigma</tex> является совершенным паросочетанием. В таком случае, <tex>perm(A)</tex> равен числу совершенных паросочетаний в графе <tex>G</tex>.
Нам известно, что задача <tex>\#SAT</tex> является <tex>\#P</tex>-полной. Аналогично задачам <tex>SAT</tex> и <tex>3SAT</tex> мы можем сказать, что задача <tex>\#SAT</tex>.
}}
