Викиконспекты - Вклад участника [ru]

Класс IP

2010-05-05T13:47:41Z

Mikhailpinsky: /* Определение */

==Определение==
Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, распознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: <tex>P</tex> - prover и <tex>V</tex> - verifier. <tex>P</tex> пытается доказать, что данная строка <tex>x</tex> принадлежит языку. <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]],
работающая за полином и проверяющая информацию от <tex>P</tex> (<tex>P</tex> не видит вероятностную ленту <tex>V</tex>). <tex>V</tex> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку. При этом:

1) <tex>x \in L => P(V^{P}(x)=1)\ge \frac{2}{3} \ </tex>

2) <tex>x \notin L => P(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </tex>

3) количество обращений к <tex>P \le f(n) </tex>

Теория сложности (старая трешовая версия)

2010-05-05T13:46:38Z

Mikhailpinsky: /* Лекция 9 */

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Класс DTIME]]
*[[Теорема о емкостной иерархии]]
*[[Теорема о временной иерархии]]
*[[Сведение по Карпу]]
*[[Сведение по Куку]]
*[[Класс P]]
*[[Класс NP]]
*[[Класс coNP]]

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Практика 2 ==
*[[Понятие NP-трудной и NP-полной задачи]]
*[[NP-полнота задачи BH1N]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме КНФ]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]
*[[NP-полнота задачи о клике]]
*[[NP-полнота задачи о независимом множестве]]
*[[NP-полнота задачи о вершинном покрытии]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задач о гамильтоновом цикле и пути в графах]]
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

== Лекция 4 ==
*[[Класс PS]]
*[[Теорема Сэвича]]
*[[PS-полнота задачи Generalized geography]]

== Лекция 6 ==
*Классы [[L]], [[NL]], [[NL-полнота|NLC]]
*[[NL-полнота задачи о достижимости в графе]]
*[[Классы EXP, NEXP. Полнота языков EXP и NEXP]]
*[[Теорема о связи вопросов EXP=NEXP и P=NP]]
*[[Теорема Иммермана]]

== Практика 6 ==
*[[Классы Sigma_i и Pi_i]]
*[[Класс PH]]
*[[Полиномиальная иерархия]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Лекция 7 ==
*[[Теорема Карпа-Липтона]]

== Практика 7 ==
*[[Вероятностная машина Тьюринга]]
*[[Класс ZPP]]
*[[Сложностные классы RP и coRP]]
*[[Сложностный класс PP]]
*[[Сложностный класс BPP]]
*[[Уменьшение ошибки в классе RP, сильное и слабое определение]]

== Лекция 8 ==
*[[Теорема о включении BPP в P/poly]]
*[[Теорема Лаутемана]]
*[[Теорема Валианта-Вазирани]]

== Практика 8 ==
*[[Лемма Шварца-Зиппеля]]

== Лекция 9 ==
*[[Класс IP|Класс IP]]
*[[GNI|Принадлежность проблемы GNI классу IP]]
*[[Sharp SAT|#SAT]]

Класс IP

2010-05-05T13:44:54Z

Mikhailpinsky: /* Определение */

==Определение==
Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, расопознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: <tex>P</tex> - prover и <tex>V</tex> - verifier. <tex>P</tex> пытается доказать, что данная строка <tex>x</tex> принадлежит языку. <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]],
работающая за полином и проверяющая информацию от <tex>P</tex> (<tex>P</tex> не видит вероятностную ленту <tex>V</tex>). <tex>V</tex> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку. При этом:

1) <tex>x \in L => P(V^{P}(x)=1)\ge \frac{2}{3} \ </tex>

2) <tex>x \notin L => P(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </tex>

3) количество обращений к <tex>P \le f(n) </tex>

Класс IP

2010-05-05T13:43:54Z

Mikhailpinsky: Новая страница: «===Определение=== Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, расопознава…»

===Определение===
Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, расопознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: <tex>P</tex> - prover и <tex>V</tex> - verifier. <tex>P</tex> пытается доказать, что данная строка <tex>x</tex> принадлежит языку. <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]],
работающая за полином и проверяющая информацию от <tex>P</tex> (<tex>P</tex> не видит вероятностную ленту <tex>V</tex>). <tex>V</tex> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку. При этом:

1) <tex>x \in L => P(V^{P}(x)=1)\ge \frac{2}{3} \ </tex>

2) <tex>x \notin L => P(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </tex>

3) количество обращений к <tex>P \le f(n) </tex>

NP-полнота задачи о независимом множестве

2010-03-19T17:53:31Z

Mikhailpinsky: /* Формулировка */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является [[Понятие NP-трудной и NP-полной задачи|NP-полной]].

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу]] задачу <math>3SAT</math> к нашей:

<math>3SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих литералов. Так же соединим ребрами пары вершин вида <math>x,\neg x</math>.

<math>(\neg x\lor y\lor z)\land (x \lor y \lor \neg z) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы один литерал, принимающий значение “истина”. Выберем соответствующую ему вершину в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют литералам из одной скобки (а мы выбирали только один литерал из каждой скобки), а так же вершины вида <math>x,\neg x</math>, соответствующие литералы которых не могут одновременно принимать значение “истина”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующего литерала “истина”. Это можно сделать, так как нет ребер между вершинами вида <math>x,\neg x</math>. Тогда в каждой скобке, будет хотя бы один литерал, имеющий значение “истина”, значит вся формула будет принимать значение “истина”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота языка CLIQUE

2010-03-19T17:52:39Z

Mikhailpinsky: /* Формулировка */

==Формулировка==
Языком CLIQUE называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку CLIQUE, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром. Задача о клике является [[Понятие NP-трудной и NP-полной задачи|NP-полной]].

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о клике является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]].
===Задача о клике принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой.

NP-полнота задачи о вершинном покрытии

2010-03-19T17:52:04Z

Mikhailpinsky: /* Формулировка */

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.

==Формулировка==
Языком COVER называется множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку COVER, если ли граф <math>G</math> содержит вершинное покрытие размера <math>k</math>. Задача о вершинном покрытии является [[Понятие NP-трудной и NP-полной задачи|NP-полной]].

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота языка CLIQUE

2010-03-19T13:46:22Z

Mikhailpinsky: /* Формулировка */

==Формулировка==
Языком CLIQUE называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку CLIQUE, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром. Задача о клике является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о клике является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]].
===Задача о клике принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой.

NP-полнота языка CLIQUE

2010-03-19T13:45:51Z

Mikhailpinsky: /* Формулировка */

==Формулировка==
Языком CLIQUE называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку CLIQUE, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>,каждая пара вершин в котором соединена ребром. Задача о клике является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о клике является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]].
===Задача о клике принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой.

NP-полнота языка CLIQUE

2010-03-19T13:43:13Z

Mikhailpinsky: /* Задача о клике является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о клике является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]].
===Задача о клике принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой.

NP-полнота языка CLIQUE

2010-03-19T13:40:25Z

Mikhailpinsky: /* Доказательство NP-полноты */

NP-полнота языка CLIQUE

2010-03-19T13:38:33Z

Mikhailpinsky: /* Доказательство NP-полноты */

NP-полнота задачи о вершинном покрытии

2010-03-19T13:36:11Z

Mikhailpinsky: /* Формулировка */

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.

==Формулировка==
Языком COVER называется множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку COVER, если ли граф <math>G</math> содержит вершинное покрытие размера <math>k</math>. Задача о вершинном покрытии является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота задачи о вершинном покрытии

2010-03-19T13:31:29Z

Mikhailpinsky: /* Задача о вершинном покрытии является NP-трудной */

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.

==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота задачи о вершинном покрытии

2010-03-19T13:31:07Z

Mikhailpinsky: /* Задача о вершинном покрытии является NP-трудной */

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.

==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства [[Сведение по Карпу||сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота задачи о независимом множестве

2010-03-19T13:28:35Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу]] задачу <math>3SAT</math> к нашей:

<math>3SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих литералов. Так же соединим ребрами пары вершин вида <math>x,\neg x</math>.

<math>(\neg x\lor y\lor z)\land (x \lor y \lor \neg z) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы один литерал, принимающий значение “истина”. Выберем соответствующую ему вершину в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют литералам из одной скобки (а мы выбирали только один литерал из каждой скобки), а так же вершины вида <math>x,\neg x</math>, соответствующие литералы которых не могут одновременно принимать значение “истина”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующего литерала “истина”. Это можно сделать, так как нет ребер между вершинами вида <math>x,\neg x</math>. Тогда в каждой скобке, будет хотя бы один литерал, имеющий значение “истина”, значит вся формула будет принимать значение “истина”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-19T13:25:49Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу]] задачу <math>3SAT</math> к нашей:

<math>3SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих литералов. Так же соединим ребрами пары вершин вида <math>x,\neg x</math>.

<math>(\neg x\lor y\lor z)\land (x \lor y \lor \neg z) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы один литерал, принимающий значение “истина”. Выберем соответствующую ему вершину в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют литералам из одной скобки(а мы выбирали только один литерал из каждой скобки), а так же вершины вида <math>x,\neg x</math>, соответствующие литералы которых не могут одновременно принимать значение “истина”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующего литерала “истина”. Это можно сделать, так как нет ребер между вершинами вида <math>x,\neg x</math>. Тогда в каждой скобке, будет хотя бы один литерал, имеющий значение “истина”, значит вся формула будет принимать значение “истина”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

Файл:IND GRAPH.png

2010-03-19T13:19:55Z

Mikhailpinsky: загружена новая версия «Файл:IND GRAPH.png»

Граф, построенный для формулы в 3-SAT

NP-полнота задачи о независимом множестве

2010-03-19T13:15:51Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу]] задачу <math>3SAT</math> к нашей:

<math>3SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\neg x</math>.

<math>(\neg x\lor y\lor z)\land (x \lor y \lor \neg z) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “истина” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\neg x</math>, соответствующие переменные которых не могут одновременно принимать значение “истина”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “истина”(с учетом отрицания). Это можно сделать, так как нет ребер между вершинами вида <math>x,\neg x</math>. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “истина”, значит вся формула будет принимать значение “истина”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-19T13:14:23Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу]] задачу <math>3SAT</math> к нашей:

<math>3SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\neg x</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “истина” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\neg x</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”(с учетом отрицания). Это можно сделать, так как нет ребер между вершинами вида <math>x,\neg x</math>. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-19T13:13:22Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу]] задачу <math>3SAT</math> к нашей:

<math>3SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\neg{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “истина” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\overline{x}</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”(с учетом отрицания). Это можно сделать, так как нет ребер между вершинами вида <math>x,\overline{x}</math>. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-19T13:01:38Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу]] задачу <math>3SAT</math> к нашей:

<math>3SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\overline{x}</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”(с учетом отрицания). Это можно сделать, так как нет ребер между вершинами вида <math>x,\overline{x}</math>. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-19T12:59:40Z

Mikhailpinsky: /* Формулировка */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром. Задача о независимом множестве является NP-полной.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\overline{x}</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”(с учетом отрицания). Это можно сделать, так как нет ребер между вершинами вида <math>x,\overline{x}</math>. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-19T12:58:06Z

Mikhailpinsky: /* Формулировка */

==Формулировка==
Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку IND, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.

==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\overline{x}</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”(с учетом отрицания). Это можно сделать, так как нет ребер между вершинами вида <math>x,\overline{x}</math>. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

Теория сложности (старая трешовая версия)

2010-03-19T09:48:02Z

Mikhailpinsky: /* Практика 2 */

Файл:IND GRAPH.png

2010-03-16T17:26:15Z

Mikhailpinsky: загружена новая версия «Файл:IND GRAPH.png»

Граф, построенный для формулы в 3-SAT

NP-полнота задачи о вершинном покрытии

2010-03-15T19:07:44Z

Mikhailpinsky: /* Доказательство NP-полноты */

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.

==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота задачи о вершинном покрытии

2010-03-15T19:07:09Z

Mikhailpinsky: /* Определение */

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.

==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота языка CLIQUE

2010-03-15T17:21:19Z

Mikhailpinsky: /* Доказательство NP-полноты */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
==Доказательство NP-полноты==
Задача о нахождении клики размера <math>k</math> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из того, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера <math>k</math> попарно не соединенных ребрами вершин.

NP-полнота задачи о независимом множестве

2010-03-15T17:18:54Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\overline{x}</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”(с учетом отрицания). Это можно сделать, так как нет ребер между вершинами вида <math>x,\overline{x}</math>. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:15:24Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\overline{x}</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:14:34Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Полученное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки), а так же вершины вида <math>x,\overline{x}</math>, соответствующие переменные которых не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:11:00Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары переменных, соответствующие вершинам вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:08:56Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:08:12Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым соответствуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:06:13Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:05:10Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о независимом множестве

2010-03-15T17:01:31Z

Mikhailpinsky:

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда”. Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о вершинном покрытии

2010-03-15T15:41:19Z

Mikhailpinsky: /* Задача о вершинном покрытии является NP-трудной */

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин
==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота задачи о независимом множестве

2010-03-14T17:57:08Z

Mikhailpinsky: /* Задача о независимом множестве является NP-трудной */

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le_{k} IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда”. Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

NP-полнота задачи о вершинном покрытии

2010-03-14T17:55:49Z

Mikhailpinsky: создание странички

==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин
==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу задачу о независимом множестве к нашей.

<math>IND \le_{k} COVER</math>

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.

Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время
===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

NP-полнота задачи о независимом множестве

2010-03-14T08:27:56Z

Mikhailpinsky: переименовал «Задача о независимом множестве» в «NP-полнота задачи о независимом множестве»: несоответствие заданию

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда”. Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

Задача о независимом множестве

2010-03-14T08:27:56Z

#перенаправление [[NP-полнота задачи о независимом множестве]]

NP-полнота языка CLIQUE

2010-03-14T08:27:00Z

Mikhailpinsky: переименовал «Задача о клике» в «NP-полнота задачи о клике»: несоответствие заданию

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
==Доказательство NP-полноты==
Задача о нахождении клики размера <math>k</math> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из того, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера хотя бы <math>k</math> попарно не соединенных ребрами вершин.

Задача о клике

2010-03-14T08:27:00Z

Mikhailpinsky: переименовал «Задача о клике» в «NP-полнота задачи о клике»: несоответствие заданию

#перенаправление [[NP-полнота задачи о клике]]

NP-полнота языка CLIQUE

2010-03-13T21:08:25Z

Mikhailpinsky: создание странички

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
==Доказательство NP-полноты==
Задача о нахождении клики размера <math>k</math> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из того, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера хотя бы <math>k</math> попарно не соединенных ребрами вершин.

NP-полнота задачи о независимом множестве

2010-03-13T15:49:37Z

Mikhailpinsky:

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда”. Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.

===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.

Файл:IND GRAPH.png

2010-03-13T15:48:02Z

Mikhailpinsky: Граф, построенный для формулы в 3-SAT

Граф, построенный для формулы в 3-SAT

NP-полнота задачи о независимом множестве

2010-03-13T15:45:36Z

Mikhailpinsky: создание странички

==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем задачу <math>3-SAT</math> к нашей:

<math>3-SAT \le IND</math>

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.

<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:Example.jpg]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда”. Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.
===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.