Изменения
→Примеры задач из #P
Преобразование графа <tex>G</tex> в <tex>G'</tex> можно выполнить за полином от количества вершин. Таким образом, если <tex>\#CYCLE \in FP</tex>, тогда сразу же <tex>HAM \in P</tex>. А так как<tex> HAM \in NP</tex>, то <tex>NP = P</tex>.
}}
==Класс #P-Complete==
{{Определение
|definition= <tex>f : \{0, 1\}^* \rightarrow \{0, 1\}^*</tex> является <tex>\#P</tex>-полной, если <tex> f \in \#P</tex> и получение для <tex>f</tex> алгоритма работающего за полиномиальное время влечет равенство <tex> \#P=FP</tex>.
}}
Для более формального определения будем использовать МТ с оракулом <tex> О = \{\big \langle x, i \big \rangle: f(x)_i = 1\}</tex>. Для нашего типа задач оракул будет отвечать на вопросы вида
