Классы 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]perm[/math]Вычислить значение перманента матрицы, заполненной нулями и единицами.
• Посчитать количество способов раскрасить заданный граф в [math]k[/math] цветов.

Теорема:

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

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

[math]\triangleright[/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]\{0,1\}[/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]\prod\limits^n_{i =1}A_{i\sigma(i)} = 1[/math] тогда и только тогда, когда [math]\sigma[/math] является совершенным паросочетанием. В таком случае, [math]perm(A)[/math] равен числу совершенных паросочетаний в графе [math]G[/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]4^m[/math] к [math]perm(A')[/math]. Тогда [math]perm(A')=4^m\cdot(\#\phi)[/math]. Для построения графа [math]G'[/math] будем использовать три вида блоков. Блок переменной. Блок каждой переменной имеет два цикла положительного веса, соответствующие присвоению 0 и 1 данной переменной. Присвоение 1 соответствует циклу, содержащему все "внешние" ребра, присвоение 0 соответствует циклу, включающему ребра-петли. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная. Блок клоза. Любой цикл для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует цикл веса 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]