Изменения

Задача вычисления перманента матрицы, элементы которой принадлежат множеству <tex>\{0,1\}</tex> может быть сведена к задаче подсчета числа совершенных паросочетаний в двудольном графе <tex>G</tex>. Тогда <tex>\prod\limits^n_{i =1}A_{i\sigma(i)} = 1</tex> тогда и только тогда, когда <tex>\sigma</tex> является совершенным паросочетанием. В таком случае, <tex>perm(A)</tex> равен числу совершенных паросочетаний в графе <tex>G</tex>. А значит задача подсчета числа совершенных паросочетаний в двудольном графе эквивалентна задаче вычисления перманента <tex>\{0,1\}-</tex>матрицы и также является <tex>\#P-</tex>полной.