Изменения
→Примеры задач из #P
== Примеры задач из #P ==
*[[#SAT]]
* <tex>\#CYCLE</tex> - имея ориентированный граф <tex>G</tex>, посчитать число простых циклов. Аналогичная задача, отвечающая на вопрос, существует ли в заданном ориентированном графе простой цикл, может быть решена за линейное время при помощи поиска в ширину. Проблема подсчета всех простых циклов значительно сложнее.*Для данного массива целых чисел посчитать количество подмножеств его элементов, таких, что сумма по всем элементам подмножества равняется 0.*Для данного взвешенного неориентированного графа посчитать количество Гамильтоновых циклов веса меньше k.
{{Теорема
Преобразование графа <tex>G</tex> в <tex>G'</tex> можно выполнить за полином от количества вершин. Таким образом, если <tex>\#CYCLE \in FP</tex>, тогда сразу же <tex>HAM \in P</tex>. А так как<tex> HAM \in NP</tex>, то <tex>NP = P</tex>.
}}
==Класс #P-Complete==
