Основні леми поліноміальній зведенності задач

Лема 1. Якщо П₁  П₂ то з П₂Р випливає, що П₁  Р (еквівалентно: з П₁Р П₂Р).

Лема 2. Якщо П₁  П₂ та П₂  П₃  П₁  П_3.

Лема 3. Якщо П₁ та П₂  NP, П₁ - NP повна та П₁  П₂  П₂  NP (NP - повна).

З цих лем випливає простий шлях доведення NP - повноти нової задачі П. Для того, щоб довести NP - повноту задачі П досить показати, що:

П  NP;

2) Відома NP-повна задача П зводиться до П.

Однак, перш ніж скористуватися цим методом доказу, необхідно знайти деяку вихідну NP – повну задачу, яку після цього можна використати для доказу NP — повноти двух задач.

1.5.Теорема кука

Фундамент теорії NP - повних задач був закладений в роботі С.Кука [3].

В цій роботі було введено поняття “зведеність за поліноміальний час”. Якщо одна задача зводиться за поліноміальний час до іншої, то будь-який поліноміальний алгоритм розв’язку другої задачі може бути перетворений в поліноміальний алгоритм розв’язку першої,

Був також визначений клас задач розпізнавання властивостей (задач, розв’язкам котрих можуть бути або “так”, або “ні”), які можуть бути вирішені ЕА (NP).

С.Кук довів, що одна конкретна задача з NP, яка називається задачею про здійсненність, має таку властивість, що будь-яка задача NP може бути зведена до неї за поліноміальний час. В деякому розумінні задача “Здійсненність” - найскладніша з NP.

Пізніше Кук та О.Карп опублікували результати, з яких видно, що досить багато відомих комбінаторних задач є такими ж складними, як і задача про здійсненність (клас NP - повних задач) [4].

Таким образом первой NP – полной задачей стала задача распознования из булевской логики. Термины, использующиеся для ее описания, определяются следующим образом.

Пусть - булевые переменные, а отрицание этих переменных. Если - истинно, то - ложна. Символы - называются литерами.

Пусть и - булевы операции “или“ и “и“. Дизьюнкт – множество литералов, объединенных операцией “или“, например

Булево выражение в коньюктивной нормальной форме ( коньюкция ) – это множество дизьюнктов, объединенных операцией “и“, например

Любое булево віражение можно представить в конїюктивной нормальной форме, используя правила Де Моргана

,

тождество

.

Булево выражение называется выполныным, если существует некоторое присваивание переменным значений ситинно и ( или ложно ), такое, что все выражение истинно. ( выполняющий набор значений истинности )

выражение ( 1 ) истинно, если , С другой стороны выражение - ложно при любом наборе переменных. Задача о выполнимости состоит в определении является ли выполнимым булево выражение в коньюктивной нормативной форме.

Сформируем задачу о выполнимости в терминах задач распознования свойств.

ВЫПОЛНИМОСТЬ ( ВЫП )

Условие. Заданы множество переменных и набор дизьюнкций над Х.

Вопрос. Существует ли выполняющий набор значений истинности для С.

Теперь можно сформировать фундаментальную теорему Кука.

Теорема Кука. Задача ВЫПОЛНИМОСТЬ есть NP – полная задача.

Доказательство теоремы Кука является достаточно сложным и не рассматривается в данном курсе. Однако, как уже указывалось, если известна одна NP – полная задача, то процедура доказательства NP – полноты других задач значительно упрощается. В дальнейшим процесс доказательства NP – полноты задачи распознования П будет состоять из следующих четырех шагов:

1) доказательства того, что П лежит в NP;

2) выбора известной NP – полной задачи П;

3) построения функции f , сводящей задачу П к задаче П;

4) доказательства того, что функція f осуществляет полиномиальное сведение.

В настоящее время известен достаточно обширный список NP – полных задач, доказательство NP – полноты которых проводилось по указанной схеме.

Теоретично будь-яку з відомих NP-повних задач можна, поряд з іншими, вибирати для доведення NP-повноти нової задачі, але деякі задачі, на практиці, виявляються для цієї мети “кращі” за інших. Наступні шість задач входять в число тих, що використовуються для цієї мети найчастіше.

Рис. 1.3.

З - ЗДІЙСНЕННІСТЬ (З - ЗДІСН)

Умова. Дан набір диз’юнкцій на кінцевій чисельності змінних Х, т.щ. С_і=3, І  і  m.

Питання. Чи існує на Х набір значень істинності, при якому виконуються всі диз’юнкції з С?