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

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

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

Утверждение 0. P ⊂ NP.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

П ∈ NP
∀ П ∈ NP ⇒ П' сводится к П

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

Теорема Кука (Cook, 1971) NPC ≠ ∅

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

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

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

$\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$

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

Утверждение. ВЫП ∈ NP

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

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

Утверждение 5. Если P ∩ NPC ≠ ∅ ⇒ P = NP, и наоборот, если найдётся П такая, что П ∈ NPC \ P, то NPC &subb; NP \ P

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

Теорема (критерий NP-полноты). Массовая задача П распознавания свойств ∈ NPC ⇔