Классы Sharp P, Sharp P-Complete — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры #P-полных задач)
(Примеры #P-полных задач)
Строка 45: Строка 45:
 
*Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.  
 
*Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.  
 
*Посчитать количество полных паросочетаний в данном двудольном графе.  
 
*Посчитать количество полных паросочетаний в данном двудольном графе.  
*Вычислить значение перманента матрицы, заполненной нулями и единицами.
+
*<tex>perm</tex>Вычислить значение перманента матрицы, заполненной нулями и единицами.
 
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
 
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
  
Строка 61: Строка 61:
 
Тогда <tex>\prod\limits^n_{i =1}A_{i\sigma(i)} = 1</tex> тогда и только тогда, когда <tex>\sigma</tex> является совершенным паросочетанием. В таком случае, <tex>perm(A)</tex> равен числу совершенных паросочетаний в графе <tex>G</tex>.  
 
Тогда <tex>\prod\limits^n_{i =1}A_{i\sigma(i)} = 1</tex> тогда и только тогда, когда <tex>\sigma</tex> является совершенным паросочетанием. В таком случае, <tex>perm(A)</tex> равен числу совершенных паросочетаний в графе <tex>G</tex>.  
  
Нам известно, что задача <tex>\#SAT</tex> является <tex>\#P</tex>-полной. Аналогично задачам <tex>SAT</tex> и <tex>3SAT</tex> мы можем сказать, что задача <tex>\#SAT</tex>.  
+
Нам известно, что задача <tex>\#SAT</tex> является <tex>\#P</tex>-полной. Аналогично задачам <tex>SAT</tex> и <tex>3SAT</tex> мы можем сказать, что задача <tex>\#SAT</tex>может быть сведена к задаче <tex>\#3SAT</tex>, которая также будет <tex>\#P</tex>-полной.
 +
 
 +
Сведем задачу  <tex>\#3SAT</tex> к задаче <tex>perm</tex>.
 +
 
 +
По данной формуле <tex>\phi</tex> с <tex>n</tex> переменными и <tex>m</tex> "клозами" построим целочисленную матрицу <tex>A'</tex> такую, что <tex>perm(A')=4^m\cdot(\#\phi)</tex>, где <tex>\#\phi -</tex> количество удовлетворяющих постановок для <tex>\phi</tex>.
 
}}
 
}}

Версия 12:05, 11 апреля 2017

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