Изменения

|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>.}}По аналогии с классом <tex>NP</tex> мы можем дать альтернативное определение определение классу <tex>\#P</tex>, используя понятие недетерменированной МТ.{{Определение |definition = '''Класс''' <tex>\#P-</tex> класс задач подсчета, решением которых является количество успешных (завершающихся в допускающих состояниях) путей вычислений для '''недетерминированной''' МТ, работающей за полиномиальное время. Отличается от большинства рассмотренных классов тем, что задачи требуют в качестве ответа не <tex>``0"</tex> или <tex>``1"</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\}^* : </tex> выполняется <tex> f(x) = | \{y \in \{0,1\}^{p(|x|)} : M(x,y) = 1 \} |</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>0,1-</tex>матрицы принадлежит классу может быть сформулирована как задача подсчета количества перестановок, для которых произведение соответствующих элементов матрицы равно <tex>\#P1</tex>. Для вычисления В такой формулировке задача нахождения перманента недетерминированно выбирается перестановка из <tex>n0,1-</tex> элементов и для каждой такой перестановки вычисляется произведение соответствующих элементов матрицы, полученные значения складываются. Время работы такого алгоритма на недетерминированной машине Тьюринга {{---}} принадлежит классу <tex>O(n)\#P</tex>по определению.

Для этого по данной 3-КНФ формуле построим ориентированный граф <tex>G'</tex> таким образом, чтобы в нем существовали покрытия циклами двух видов: те, которые соответствуют удовлетворяющим назначениям, и те, которые не соответствуют. Назовем покрытием ориентированного графа циклами такой подграф, что для любой вершины есть ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда <tex>perm(A)</tex> равен сумме весов всех возможных покрытий циклами. Далее покажем, что любое удовлетворяющее назначение для формулы <tex>\phi</tex> будет добавлять <tex>4^m</tex> к <tex>perm(A')</tex>, а остальные любое другое назначение не будут будет вносить вклад. Тогда <tex>perm(A')=4^m\cdot(\#\phi)</tex>.

Теперь сведем полученную матрицу к <tex>0,1-</tex>матрице. Для начала изменим веса ребер так, чтобы они были равны <tex>\pm1</tex>. Заметим, что замена ребра веса <tex>k</tex> на <tex>k</tex> параллельных ребер веса <tex>1</tex> не меняет перманента матрицы. В графе не допускаются параллельные ребра, но мы можем сделать их допустимыми, если разобьем каждое из них на два, добавив новые вершины. Чтобы избавиться от ребер с отрицательным весом, заметим, что перманент графа <tex>G</tex> с весами ребер равными <tex>\pm1</tex> равен числу из отрезка <tex>[-n!, \, n!]</tex> и может быть вычислен как <tex>y = x \, ( mod \, 2^{m+1})</tex>, где <tex>m</tex> достаточно большое (например, <tex>m = n^2</tex>. Для того, чтобы вычислить <tex>y</tex> , достаточно посчитать перманент матрицы смежности графа, где все ребра веса <tex>-1</tex> заменены на ребра веса <tex>2^m</tex>. Эти ребра могут быть заменены на <tex>m</tex> ребер весом <tex>2</tex>, которые можно разбить на двойки параллельных ребер весом <tex>+1</tex>, как на предыдущем шаге.

Таким образом для данной нам формулы мы за полиномиальное время построили соответствующий граф <tex>G'</tex> такой, что <tex>perm(A') = 4^m\cdot(\#\phi)</tex>, где <tex>A'</tex> - матрица смежности графа <tex>G'</tex> и свели задачу <tex>\#3SAT</tex> к задаче <tex>perm</tex>. Значит задача <tex>perm</tex> является <tex>\#P-</tex>-полной.

[[Категория: Теория Классы сложности]]