Редактирование: Методы оптимизации, 02 лекция (от 15 февраля)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

//отсутствует первая половина лекции

Утверждение 0. P &sub; NP.

Основной вопрос — вопрос строгого включения. Не удоаётся доказать ни то, что P строго включается в NP, ни то, что он равен NP. Сейчас господствует гипотеза строгого включения, но не исключено и обратное.

Прдположение о том, что у нас имеется строгое включение... мы хотим определить те задачи, котрые в случае строгого включения не попадут в класс P. Для того, чтобы ввести такие здаачи, нам понадобится понятие «одна задача сложнее другой». Например: за полиномиальное время из алгоритма решения первой задачи можно а полин. время получить второй, или привести алгоритм решения первой к алгоритму решения второй

Опрееделение 6. Массовая задача распознавания свойств П' с кодировкой e' полиномиально сводится к П с e, если у нас <math>\exist f: e'(\Pi') \darr e(\Pi)<math>, это значит, что <math>f(e'(Y')) = e(Y)<math> и существует детерминированная МТ A<sub>f</sub>, которая реализует f за полиномиальное время.

Далее будем писать <math>\Pi' \profto(?) \Pi</math> (значёк бесконечности с отгрызенной правой частью) --- полиномиальная сводимость

Этот значёк можно воспринимать как знак нестрогого порядка.

Утверждение 2. Если П1 сводится к П2 и П2 к П3, то (транзитивность сводимости) П1 сводится к П3

Доказательство основано на том, что полином от полинома — полином.

Утв. 3. Если П' полиномиально сводится к П и П &isin; '''P''', то П' &isin; '''P'''.

Доказательство. <math>\exist A \exist p(.)</math>. Построим алгоритм A', решающий задачу П': <math>A' = A \times A_f I' \in \Pi' \overbrace{\rArr}{A_f} I \in \Pi {overbrace}{\dArr}{A} </amth> решение, <math>t_{A'}(I') \le p(P_f(|I|))</math>.

Соврешенно аналогично получаем

Утверждение 4. Если П' полиномиально сводится к П и П &isin; '''NP''', то П' &isin; '''NP'''.

Доказательство аналогично.

Основное определение всей теории сложности:

Определение 7. Массовая задача П называется '''NP'''-полной, или, иначе, универсальной, обозначение '''NPC''' (NP-complete), если 
# П &isin; '''NP'''
# &forall; П &isin; '''NP''' &rArr; П' сводится к П

С определения этого класса пошла теория сложности как теория, и основной теоремой теории сложности является теорема Кука (1971 год):

Теорема Кука (Cook, 1971) '''NPC''' &ne; &empty;

В частности, задача выполнимости (ВЫП) принадлежит '''NPC'''

Эта теорема будет доказываться на 5 курсе.

ВЫП: &exist; выполняющий набор для КНФ?

<math>\And_{i=1}^{N} D_i(z), D_i(z) = \Or_{j = 1}^{n_j} z_j^(\alpha_j), z_j^0 = \empty, z_j^1 = z_j, z_j^{-1} = \not z_j</math>

Соответственно, задача состоит в &exist; z: КНФ(z) = 1.

Утверждение. ВЫП &isin; '''NP'''

Доказательство. Предположим, что ответ да. Тогда &exists;z с волной, КНФ(z с волной) = 1. Для проверки надо подстваить аргумент в КНФ, что все дизьюнкты равны 1, проверка имеет линейную сложность, проверка полиномиальная.

Почему так хороши, важны, интересны NP-полные задачи?

Утверждение 5. Если '''P''' &cap; '''NPC''' &ne; &empty; &rArr; '''P''' = '''NP''', и наоборот, если найдётся П такая, что П &isin; '''NPC''' \ '''P''', то '''NPC''' &subb; '''NP''' \ '''P'''

В книге Грея-Джонсона приведено более 500 задач из класса NPС, и все задачи остальные, их принадлежность к классу NPC доказывалась не напрямую, а доказывалась на основании следующего критерия:

Теорема (критерий NP-полноты). Массовая задача П распознавания свойств &isin; '''NPC''' &hArr; 
# П &isin; '''NP'''
# &exist; П* &isin; '''NPC''', П* полиномиально сводится к П.

Доказательство (по транзитивности). &forall; П' &isin; '''NP''', П' полиномильано сводится к П* полиномиально сводится к П.

Утвеждение. БЛН (задача булевых линейных неравенств) &isin; """NPC'''

Доказательство. ВЫП сводится к БЛН

Задача БЛН:
<math>\exist z \in \mathbb{B}^n (система)
a_11 z_1 + ... + a_1n z_n \le b_1\
...\
a_m1 z_1 + ... + a_mn z_n \le b_m</math>

эквивалентная проверка: z_1 \or \not z_2 \or z_4 || z_1 + (1 - z_2) + z_4 \ge 1

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_15_%D1%84%D0%B5%D0%B2%D1%80%D0%B0%D0%BB%D1%8F%29

Редактирование: Методы оптимизации, 02 лекция (от 15 февраля)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 7: / Строка 7: @@
 Прдположение о том, что у нас имеется строгое включение... мы хотим определить те задачи, котрые в случае строгого включения не попадут в класс P. Для того, чтобы ввести такие здаачи, нам понадобится понятие «одна задача сложнее другой». Например: за полиномиальное время из алгоритма решения первой задачи можно а полин. время получить второй, или привести алгоритм решения первой к алгоритму решения второй
-Опрееделение 6. Массовая задача распознавания свойств П' с кодировкой e' полиномиально сводится к П с e, если у нас
+Опрееделение 6. Массовая задача распознавания свойств П' с кодировкой e' полиномиально сводится к П с e, если у нас <math>\exist f: e'(\Pi') \darr e(\Pi)<math>, это значит, что <math>f(e'(Y')) = e(Y)<math> и существует детерминированная МТ A<sub>f</sub>, которая реализует f за полиномиальное время.
-<math>\exist f: e'(\Pi') \darr e(\Pi)</math>,
-это значит, что
-<math>f(e'(Y')) = e(Y)</math>
-и существует детерминированная МТ A<sub>f</sub>, которая реализует f за полиномиальное время.
-Далее будем писать <math>\Pi' \propto(?) \Pi</math> (значёк бесконечности с отгрызенной правой частью) --- полиномиальная сводимость
+Далее будем писать <math>\Pi' \profto(?) \Pi</math> (значёк бесконечности с отгрызенной правой частью) --- полиномиальная сводимость
 Этот значёк можно воспринимать как знак нестрогого порядка.
@@ Строка 23: / Строка 19: @@
 Утв. 3. Если П' полиномиально сводится к П и П &isin; '''P''', то П' &isin; '''P'''.
-Доказательство. <math>\exist A \exist p(.)</math>. Построим алгоритм A', решающий задачу П': <math>A' = A \times A_f I' \in \Pi' \overbrace{\rArr}{A_f} I \in \Pi \overbrace{\dArr}{A} </math> решение, <math>t_{A'}(I') \le p(P_f(|I|))</math>.
+Доказательство. <math>\exist A \exist p(.)</math>. Построим алгоритм A', решающий задачу П': <math>A' = A \times A_f I' \in \Pi' \overbrace{\rArr}{A_f} I \in \Pi {overbrace}{\dArr}{A} </amth> решение, <math>t_{A'}(I') \le p(P_f(|I|))</math>.
 Соврешенно аналогично получаем
@@ Строка 47: / Строка 43: @@
 ВЫП: &exist; выполняющий набор для КНФ?
-<math>\And_{i=1}^{N} D_i(z), D_i(z) = \lor_{j = 1}^{n_j} z_j^(\alpha_j), z_j^0 = \empty, z_j^1 = z_j, z_j^{-1} = \not z_j</math>
+<math>\And_{i=1}^{N} D_i(z), D_i(z) = \Or_{j = 1}^{n_j} z_j^(\alpha_j), z_j^0 = \empty, z_j^1 = z_j, z_j^{-1} = \not z_j</math>
 Соответственно, задача состоит в &exist; z: КНФ(z) = 1.
@@ Строка 72: / Строка 68: @@
 Задача БЛН:
-<math>
+<math>\exist z \in \mathbb{B}^n (система)
-\exist z \in \mathbb{B}^n
+a_11 z_1 + ... + a_1n z_n \le b_1\
-\begin{cases}
+...\
-a_11 z_1 + ... + a_1n z_n \le b_1 \\
+a_m1 z_1 + ... + a_mn z_n \le b_m</math>
-... \\
-a_m1 z_1 + ... + a_mn z_n \le b_m
-\end{cases}
-</math>
-эквивалентная проверка:
+эквивалентная проверка: z_1 \or \not z_2 \or z_4 || z_1 + (1 - z_2) + z_4 \ge 1
-<math>z_1 \or \not z_2 \or z_4 || z_1 + (1 - z_2) + z_4 \ge 1</math>
 {{Методы оптимизации}}
 {{Lection-stub}}