Изменения

Для более формального определения будем использовать МТ с оракулом <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> множество функций, вычислимых за полиномиальное время на МТ с оракулом для функции f. Тогда <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>.