Классы 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]\triangleleft[/math]