Изменения
→Примеры #P-полных задач
|proof=
{{Определение
|definition =Перманентом матрицы А размером <tex>n x \times n</tex> называется <tex>perm(aA) = \sum \limits_{\sigma \in S_n} \prod\limits^n_{i =1}A_{i\sigma(i)}</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\limits^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>.
}}
