Изменения

|definition ='''Класс''' <tex>\#P-</tex> класс задач, решением которых является количество успешных (завершающихся в допускающих состояниях) путей вычислений для '''недетерминированной ''' МТ, работающей за полиномиальное время. Отличается от большинства рассмотренных классов тем, что задачи требуют в качестве ответа не <tex>``0"</tex> или <tex>``1"</tex>, а натуральное число.<br> Более формально: <tex>f : \{0,1\}^* \rightarrow \mathbb{N}</tex> принадлежит <tex>\#P</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время '''недетерминированная ''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* : f(x) = | \{y \in \{0,1\}^{p(|x|)} : M(x,y) = 1 \} |</tex>.

|definition ='''Класс''' <tex>\mathrm{FP}</tex> {{---}} класс задач подсчета, разрешимых на '''детерминированной ''' машине Тьюринга за полиномиальное время, то есть:<tex>f : \{0,1\}^* \rightarrow \mathbb{N}</tex> принадлежит <tex>FP</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время '''детерминированная ''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* : f(x) = | \{y \in \{0,1\}^{p(|x|)} : M(x,y) = 1 \} |</tex>