Изменения
→Классы #P и #P-Complete
<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>.
}}
Вопрос, являются ли задачи из <tex>\#P</tex> //эффективно разрешимыми// остается открытым. Класс <tex>FP</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>, так как подсчет числа сертификатов может быть выполнен за полиномиальную память. == Примеры задач из <tex>\#P</tex> ==*[[#SAT]]* <tex>\#CYCLE</tex>
