41
правка
Изменения
→Примеры #P-Complete задач
Задача вычисления перманента матрицы, элементы которой принадлежат множеству <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>.
==Источники==
*[http://theory.cs.princeton.edu/complexity/book.pdf Christos H. Papadimitriou. Computational Complexity. c. 172-179]
*[https://en.wikipedia.org/wiki/Counting_problem_(complexity) Counting problem]
*[https://en.wikipedia.org/wiki/Sharp-P Sharp-P ]
*[https://en.wikipedia.org/wiki/Sharp-P-complete Sharp-P-complete]
*[https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent Sharp-P-completeness of 01-permanent]
*[https://shaih.github.io/pubs/01perm.pdf Zero One Permanent is #P-Complete, A Simpler Proof]
== См. также ==
*[[Класс P]]
*[[Классы NP, coNP, Σ₁, Π₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
[[Категория: Теория сложности]]
