Изменения

Для более формального определения будем использовать МТ с оракулом <tex> O = \{\big \langle x, i \big \rangle: f(x)_i = 1\}</tex> для нашей функции <tex>f</tex>. Для нашего типа задач оракул будет отвечать на вопросы вида "Принадлежит ли слово <tex>q</tex> языку <tex>O</tex>?" за один шаг на МТ. Для функции <tex>f = \{0,1\}^* \rightarrow \{0, 1\}^*</tex> будем называть <tex>FP^f</tex> множество функций, вычислимых за полиномиальное время на МТ с оракулом для функции <tex>f</tex>.

Тогда <tex>f - \#P</tex>-полная, если <tex>f \in \#P</tex> и любая <tex>g \in \#P</tex> принадлежит <tex>FP^f</tex>.

Если <tex>f \in FP </tex>, тогда <tex>FP=FP^f</tex>. Получаем, что, если <tex>f - \#P</tex>-полная и <tex>f \in FP</tex>, то <tex>FP=\#P</tex>. Для множества языков из <tex>NP</tex> (таких как <tex>3SAT, CLIQUE, Ham </tex>) существуют их версии из <tex>\#P</tex>. См. <tex>\#SAT</tex>.