Изменения
→Класс #P-Complete
Для множества языков из <tex>NP</tex> (таких как <tex>3SAT, CLIQUE, Ham </tex>) существуют их версии из <tex>\#P</tex>. См. <tex>\#SAT</tex>.
== Примеры #P-полных задач ==
Многие задачи из класса <tex>\#P-</tex>полных получаются из задач разрешимости из класса <tex>P</tex> за счет требования подсчета всевозможных удовлетворяющих наборов входных значений.
*[[#SAT]]
* Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.
*Посчитать количество полных паросочетаний в данном двудольном графе.
*Вычислить значение перманента матрицы, заполненной нулями и единицами.
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
