Изменения

|definition= <tex>f : \{0, 1\}^* \rightarrow \{0, 1\}^*</tex> является <tex>\#P</tex>-полной, если <tex> f \in \#P</tex> и получение для любая проблема из <tex>f\#P</tex> алгоритма работающего может быть сведена к ней за полиномиальное время влечет равенство <tex> \#P=FP</tex>.

Для более формального определения будем Будем использовать МТ с оракулом <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>.