Изменения
→Класс #P
<tex>f : \{0,1\}^* \rightarrow \mathbb{N}</tex> принадлежит <tex>FP</tex>, если существует <tex>p \in Poly</tex> и работающая за полиномиальное время '''детерминированная''' машина Тьюринга <tex>M</tex> такая, что для любого <tex>x \in \{0,1\}^* </tex> выполняется <tex> f(x) = M(x)</tex>.
}}
Вопрос, являются ли задачи из <tex>\#P</tex> эффективно разрешимыми, остается открытым. Подсчет числа сертификатов как минимум столь же сложен, как и проверка наличия сертификата, а значит, если , доказать равенство <tex>\#P=FP</tex>, то автоматически будет доказано <tex>NP=P</tex>. Однако , из <tex>NP=P</tex> вовсе не следует <tex>\#P=FP</tex>. Также можно заметить, что если <tex>PSPACE = P</tex>, то <tex>\#P=FP</tex>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память.
== Примеры задач из #P ==
