41
правка
Изменения
→Примеры #P-полных задач
Если <tex>f \in FP </tex>, тогда <tex>FP=FP^f</tex>. Получаем, что, если <tex>f - \#P</tex>-полная и <tex>f \in FP</tex>, то <tex>FP=\#P</tex>.
== Примеры #P-полных Complete задач ==
Многие задачи из класса <tex>\#P-</tex>полных получаются из задач разрешимости из класса <tex>P</tex> за счет требования подсчета всевозможных удовлетворяющих наборов входных значений.
*[[#SAT]]
