Классы Sharp P, Sharp P-Complete

Класс #P

Определение:

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

Вопрос, являются ли задачи из [math]\#P[/math] //эффективно разрешимыми// остается открытым. Класс [math]FP[/math] - аналог класса [math]P[/math] для задач, ответ на которые представляется не битовым значением, а натуральным числом. Подсчет числа сертификатов как минимум столь же сложно, как и проверка наличия сертификата, а значит, если доказать равенство [math]\#P=FP[/math], то автоматически будет доказано [math]NP=P[/math]. Однако из [math]NP=P[/math] вовсе не следует [math]\#P=FP[/math]. Если [math]PSPACE = P[/math], то [math]\#P=FP[/math], так как подсчет числа сертификатов может быть выполнен за полиномиальную память.

Примеры задач из #P

• #SAT
• [math]\#CYCLE[/math] - имея ориентированный граф [math]G[/math], посчитать число простых циклов. Аналогичная задача, отвечающая на вопрос, существует ли в заданном ориентированном графе простой цикл, может быть решена за линейное время при помощи поиска в ширину. Проблема подсчета всех простых циклов значительно сложнее.
• Для данного массива целых чисел посчитать количество подмножеств его элементов, таких, что сумма по всем элементам подмножества равняется 0.
• Для данного взвешенного неориентированного графа посчитать количество Гамильтоновых циклов веса меньше k.

Теорема:

Если [math]\#CYCLE \in FP[/math], тогда [math]P=NP[/math].

Доказательство:

[math]\triangleright[/math]

[math]deg^{-}+deg^{+}=10=2\cdot |E|[/math] Для графа [math]G[/math] с n вершинами построим граф [math]G'[/math] такой, что в [math]G[/math] есть Гамильтонов цикл тогда и только тогда, когда в [math]G'[/math] есть [math]n^{n^2}[/math] циклов. Чтобы получить [math]G'[/math], заменим каждое ребро [math](u,v)[/math] из [math]G[/math] на блок [math]H[/math]. Блок состоит из [math]m = n * \log{n} + 1[/math] уровней. [math]G[/math] представляет из себя ацикличный граф, а значит циклы в [math]G'[/math] соответствуют циклам в [math]G[/math]. Кроме того, существует [math]2^m[/math] различных путей между [math]u[/math] и [math]v[/math] внутри блока, следовательно простому циклу длины [math]l[/math] в [math]G[/math] соответствует цикл длины [math]2^{(ml)}[/math] в [math]G'[/math]. Заметим, что если граф [math]G[/math] содержит гамильтонов цикл, то в [math]G'[/math] существует минимум [math]2^{m(n-1)} \gt n^{n^2}[/math] циклов. Проверим в обратную сторону. Если в [math]G[/math] не существует Гамильтонова цикла, то самый длинный цикл в [math]G[/math] имеет длину не больше [math]n-1[/math] и число циклов не может превысить [math]n^{n-1}[/math]. Таким образом, в [math]G'[/math] будет не более чем [math](2^m)^{n-1} * n^{n-1} \lt n^{n^2}[/math] циклов.му входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа чётна и равна удвоенному числу рёбер. Преобразование графа [math]G[/math] в [math]G'[/math] можно выполнить за полином от количества вершин. Таким образом, если [math]\#CYCLE \in FP[/math], тогда сразу же [math]HAM \in P[/math]. А так как[math] HAM \in NP[/math], то [math]NP = P[/math].

[math]\triangleleft[/math]

Класс #P-Complete

Определение:

[math]f : \{0, 1\}^* \rightarrow \{0, 1\}^*[/math] является [math]\#P[/math]-полной, если [math] f \in \#P[/math] и получение для [math]f[/math] алгоритма работающего за полиномиальное время влечет равенство [math] \#P=FP[/math].

Для более формального определения будем использовать МТ с оракулом [math] O = \{\big \langle x, i \big \rangle: f(x)_i = 1\}[/math] для нашей функции [math]f[/math]. Для нашего типа задач оракул будет отвечать на вопросы вида "Принадлежит ли слово [math]q[/math] языку [math]O[/math]?" за один шаг МТ. Для функции [math]f = \{0,1\}^* \rightarrow \{0, 1\}^*[/math] будем называть [math]FP^f[/math] множество функций, вычислимых за полиномиальное время на МТ с оракулом для функции [math]f[/math].

Тогда [math]f - \#P[/math]-полная, если [math]f \in \#P[/math] и любая [math]g \in \#P[/math] принадлежит [math]FP^f[/math].

Если [math]f \in FP [/math], тогда [math]FP=FP^f[/math]. Получаем, что, если [math]f - \#P[/math]-полная и [math]f \in FP[/math], то [math]FP=\#P[/math].

Для множества языков из [math]NP[/math] (таких как [math]3SAT, CLIQUE, Ham [/math]) существуют их версии из [math]\#P[/math]. См. [math]\#SAT[/math].

Примеры #P-полных задач

Многие задачи из класса [math]\#P-[/math]полных получаются из задач разрешимости из класса [math]P[/math] за счет требования подсчета всевозможных удовлетворяющих наборов входных значений.

• #SAT
• Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.
• Посчитать количество полных паросочетаний в данном двудольном графе.
• Посчитать количество способов раскрасить заданный граф в [math]k[/math] цветов.
• Вычислить значение перманента матрицы, заполненной нулями и единицами.

Определение:

Перманентом матрицы А размером [math]n \times n[/math] называется[math]perm(A) = \sum\limits_{\sigma \in S_n} \prod\limits^n_{i =1}A_{i\sigma(i)}[/math], где [math]S_n -[/math] множество всех перестановок из n элементов.

Теорема:

Задача вычисления перманента матрицы, заполненной нулями и единицами является [math]\#P-[/math]полной.

Доказательство:

[math]\triangleright[/math]

Далее будем рассматривать матрицу [math]A'[/math] как матрицу смежности двудольного графа [math]G'[/math] : [math]X = \{x_1, …, x_n\}, \, Y = \{y_1, …, y_n\}, \, \{x_i, y_j\} \in V(G) \iff A_{i, j} = 1[/math]. Назовем покрытие ориентированного графа циклами такой подграф, что для любой вершины есть ровно одно входящее и исходящее ребро. Такой подграф должен состоять из циклов. Определим вес покрытия как произведение весов ребер, входящих в него. Тогда [math]perm(A)[/math] равен сумме весов всех возможных покрытий циклами. Нам известно, что задача [math]\#SAT[/math] является [math]\#P[/math]-полной. Аналогично задачам [math]SAT[/math] и [math]3SAT[/math] мы можем сказать, что задача [math]\#SAT[/math] может быть сведена к задаче [math]\#3SAT[/math], которая также будет [math]\#P[/math]-полной. Сведем задачу [math]\#3SAT[/math] к задаче [math]perm[/math]. По данной формуле [math]\phi[/math] с [math]n[/math] переменными и [math]m[/math] клозами построим целочисленную матрицу [math]A'[/math] такую, что [math]perm(A')=4^m\cdot(\#\phi)[/math], где [math]\#\phi -[/math] количество удовлетворяющих подстановок для [math]\phi[/math]. Построим граф [math]G'[/math] таким образом, чтобы в нем существовали покрытия циклами двух видов: те, которые соответствуют удовлетворяющим назначениям, и те, которые не соответствуют. Покажем, что любое удовлетворяющее назначение для формулы [math]\phi[/math] будет добавлять [math]4^m[/math] к [math]perm(A')[/math]. Тогда [math]perm(A')=4^m\cdot(\#\phi)[/math]. Для построения графа [math]G'[/math] будем использовать три вида блоков. Блок переменной. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению true или false данной переменной. Присвоение true соответствует покрытию, содержащему все "внешние" ребра, присвоение false соответствует циклу, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная. Блок клоза. Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует покрытие веса 1. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменной, присутствующей в нем. Блок [math]XOR[/math]. Цель данного клоза - убедиться, что для произвольной пары ребер [math]uu'[/math] и [math]vv'[/math] ровно одно из них присутствует в любом из покрытий циклами, учитывающемся в итоговой сумме. Допустим, мы заменяем пару ребер [math]uu'[/math] и [math]vv'[/math] на блок XOR. Каждый цикл в [math]G[/math] веса [math]w[/math], проходящий через ровно одно из ребер [math]uu'[/math] и [math]vv'[/math], превращается в набор циклов в графе [math]G'[/math] общим весом [math]4w[/math]: вклад дает набор циклов, которые заходят в блок через [math]u[/math] и выходят через [math]u'[/math] или заходят через [math]v[/math] и выходят через [math]v'[/math], вес остальных циклов в сумме равняется [math]0[/math] и при дальнейшем подсчете мы можем их не учитывать. Блок [math]XOR[/math]'a соединяет блоки переменных с соответствующими блоками клозов так, чтобы вклад в общую сумму вносили только те циклы, которые соответствуют удовлетворяющим назначениям нашей формулы. Рассмотрим клоз и переменную внутри него. Рассмотрим внешние ребра соответствующих блоков и соединим их при помощи [math]XOR[/math]-блока. Теперь если при построении цикла мы не проходим через внешнее ребро клоза, то мы гарантированно проходим по внешнему ребру переменной, что аналогично присвоению переменной значения true. Так как хотя бы одно ребро в каждом блоке клоза будет пропущено, то каждый цикл, который мы учитываем соответствует удовлетворяющему назначению. А для каждого удовлетворяющего назначения существует множество циклов суммарным весом [math]4^{3m}[/math], так как они проходят через блоки [math]XOR[/math] ровно [math]3m[/math] раз. Таким образом [math]perm(G') = 4^{3m}\#\phi[/math]. Теперь сведем полученную матрицу к 0,1-матрице. Для начала изменим веса ребер так, чтобы они были равны [math]\pm1[/math]. Заметим, что замена ребра веса [math]k[/math] на [math]k[/math] параллельных ребер веса [math]1[/math] не меняет перманента матрицы. В графе не допускаются параллельные ребра, но мы можем сделать их допустимыми, если разобьем каждое из них на два, добавив новые вершины. Чтобы избавиться от ребер с отрицательным весом, заметим, что перманент графа [math]G[/math] с весами ребер равными [math]\pm1[/math] равен числу из отрезка [math][-n!, \, n!][/math] и может быть вычислен как [math]y = x \, ( mod \, 2^{m+1})[/math], где [math]m[/math] достаточно большое (например, [math]m = n^2[/math]. Для того, чтобы вычислить [math]y[/math] достаточно посчитать перманент графа, где все ребра веса [math]-1[/math] заменены на ребра веса [math]2^m[/math]. Эти ребра могут быть заменены на [math]m[/math] ребер весом [math]2[/math], которые можно разбить на двойки параллельных ребер весом [math]+1[/math], как на предыдущем шаге.

[math]\triangleleft[/math]

Замечание

Задача вычисления перманента матрицы, элементы которой принадлежат множеству [math]\{0,1\}[/math] может быть сведена к задаче подсчета числа совершенных паросочетаний в двудольном графе [math]G[/math]. Тогда [math]\prod\limits^n_{i =1}A_{i\sigma(i)} = 1[/math] тогда и только тогда, когда [math]\sigma[/math] является совершенным паросочетанием. В таком случае, [math]perm(A)[/math] равен числу совершенных паросочетаний в графе [math]G[/math].