Ііі. Побудова компонентів

Доведення NP-повноти задач 3  СПОЛ, ВП та ГЦ  типові приклади. Основна ідея таких доведень полягає в тому, щоб за допомогою складових частин розглянутої задачі сконструювати деякі “компоненти”, поєднуючи які можна “реалізувати” індивідуальні задачі відомої NP-повної задачі.

Пари близьких задач, одна  р, інша np-повна

P	NP
Найкоротший шлях між двома вершинами	Найдовший шлях між двома вершинами
Умова. Задан граф G=(V, E), довжина l(e)Z+ для кожної eE, виділені вершини а, bV та BZ+.	Умова. Задан граф G=(V, E), дов - жина l(e)Z+ для кожної eE, Виділені вершини а, bV та BZ+.
Питання. Існує чи ні в G простий шлях з a в b, який має довжину не більше за В?	Питання. Існує чи ні в G простий шлях з a в b, який має довжину не менше за В?

Реберне покриття	Вершинне покриття
Умова. Задан граф G=(V, E) та КZ+ .	Умова. Заданий граф G=(V, E) та КZ+ .
Питання. Існує EE т.,ч /E/К та для кожної вершини vV є таке ребро eE, що vE?	Питання. Існує VV т.,ч /V/К та для кожного ребра eE є така вершина vV, що V e?

Розклад для прямого дерева завдань	Розклад для зворотнього дерева завдань
Умова. Задані: множина Т завдань з одиничною тривалістю, директивний строк d(t)Z+ для кожного tT, частковий порядок  на множині Т, відносно якого кожне завдання має не більш одного безпосередньо наступного за ним, mZ+.	Умова. Задані: множина Т завдань з одиничною тривалістю, директивний строк d(t)Z+ для кожного tT, частковий порядок  на множині Т, відносно якого кожне завдання має не більш одного безпосередньо попередника.
Питання. Можна чи ні скласти для множини Т розклад на m процесорах, так, що виконується частковий порядок та директивні строки.	Питання. Можна чи ні скласти для множини Т розклад на m процесорах, так, що виконується частковий порядок та директивні строки.

1.6.Аналіз підзадач

1.7.Розмальовування графа в 3 кольори

Умова. Задан граф G = (V, E)

Питання. Чи вірно, що G розмальовується в три кольори ? Чи існує така функція , що , якщо .

Розглянемо обмеження максимальної степені вершин для задач теорії графів. Більшість задач з теорії графів може бути вирішено за поліноміальний час, якщо максимум степенів вершин графів достатньо малий.

	P при D	NP при D
Вершинне покриття	2	3
Гамільтонов цикл	2	3
Розмальовуваність графів в три кольори	3	4
Множина вершин, що розрізують контур	2	3

Необхідність аналізу підзадач NP повної задачі особливо яскраво проявляється в задачах з числовими параметрами. Покажемо це на прикладі розв’язання задачі РОЗБИТТЯ методом "динамічного програмування".

j i

0

1

2

3

4

5

6

7

8

9

10

11

12

13

1

T

T

F

F

F

F

F

F

F

F

F

F

F

F

1

2

T

T

F

F

F

F

F

F

F

T

T

F

F

F

9

3

T

T

F

F

F

T

T

F

F

T

T

F

F

F

5

4

T

T

F

T

T

T

T

F

T

T

T

F

T

T

3

5

T

T

F

T

T

T

T

F

T

T

T

T

T

T

8

S(a₁) = 1; S(a₂) = 9; S(a₃) = 5; S(a₄) = 3; S(a₅) = 8; B = 26.

Таблиця заповнюється послідовно рядок за рядком зверху вниз.

В першому рядку t(1, j) = T необхідно і достатньо чи j = 0, чи j = S(a₁). Кожний наступний рядок заповнюється з урахуванням значень в попередньому рядку. Для 1< j n, 0 j B/2, рівність t( i, j ) = T має місце, необхідно і достатньо чи t( i-1, j ) = T, чи якщо S( a_i ) j і t( i-1, j-S( a_i ) ) = T. Задача РОЗБИТТЯ буде вирішена, якщо t( n, B/2 ) = T.

Час роботи алгоритму обмежений поліномом від кількості клітинок таблиці (від nB). На перший погляд може здатись, що ми отримали поліноміальний алгоритм. Однак, це не так. Наявність такого алгоритму показує, що NP повнота задачі РОЗБИТТЯ залежить від величини цифр на вході. Якщо б на величину таких чисел було би заздалегідь накладене обмеження, наприклад у вигляді поліному від Length , то алгоритм був би поліноміальним (будемо називати такі алгоритми псевдополіноміальними). Введемо дві функції Length: і Мах: . Призначення функції Length полягає в порівнянні будь-якої індивідуальній задачі I деякого цілого числа Length (I), що відповідає числу символів, які використовуються при описі I. Призначення функції Мах полягає в порівнянні індивідуальної задачі I цілого числа Мах , що відповідає величині максимального числа в І.

Алгоритм розв’язку задачі П будемо називати псевдополіноміальним по часу алгоритмом, якщо його часова функція обмежена зверху поліномом від двох аргументів Length і Мах .

Будь-який поліноміальний алгоритм є також псевдополіноміальним, обмеженим поліномом від одного аргументу - Length .

Будемо називати задачу П задачею з числовими параметрами, якщо не існує такого поліному р, що Мах р (Length ) для всіх ІDп.

Зауваження. Якщо NP-повна задача П не є задачею з числовими параметрами, то П не може бути вирішена псевдополіноміальним алгоритмом.

Для довільної задачі П та поліному р позначимо Пр підзадачу, яку отримуємо з П розгляданням тільки тих індивідуальних задач, для яких Мах р (Length ). Задача Пр - не є задачею з числовими параметрами.

Задачу П назвемо NP-повною в сильному значенні, якщо П належить NP та існує поліном р, що задача Пр є NP-повною.

Наприклад, для задачі комівояжер задачею Пр може служити задача Шлях Гамільтона.

Задача. Розклад для мультипроцесорної системи та Упорядкування всередині інтервалів NP-повні в сильному значенні, а задача РЮКЗАК - ні.

Приведемо сьому задачу, яку будемо використовувати для доведення сильної NP-повноти.

З-Розбиття

Умова. Задані множина А, яка складається з Зт елементів, границя ВZ⁺ та розміри S(a)Z⁺ всіх елементів, аА, причому В/4 S(a) В/2 та .

Питання. Можна чи ні А так розбити на т непересічених підчисельностей S₁, S₂, ... , S_m, що для І  i  т (кожна множина містить рівно 3 елементи).

Теорема. Задача З-Розбиття NP-повна в сильному значенні.

Нехай П та П - довільні задачі розпізнання; Dп та Dп - чисельності їх індивідуальних задач; Уп та Уп - чисельності індивідуальних задач з відповіддю “так” Мах, Length, Мах, Length - відповідні функції довжини та максимуму. Задача П псевдополіноміально зводиться до задачі П, якщо існує функція f: DпDп, котра володіє такими властивостями:

а) для  ID, IУп тоді і тільки тоді, коли f(I)Eп.

б) функція f може бути обчислена за час, що обмежений поліномом від двох змінних Мах і Length .

в) існує такий поліном q₁, що для всіх IDп має місце нерівність

q₁(Length[f(I)]) Length(I);

г) існує такий поліном q₂ від двох змінних, що для всіх IDп виконана нерівність

Мах[f(I)]  q₂(Мах , Length ).

Лема. Якщо П - NP-повна в сильному значенні задача, ПNP та П псевдополіноміально зводиться до П, то П - NP-повна в сильному значенні задача.

Для прикладу, скористаємося псевдополіноміальною зведеністю для доведення сильної NP-повноти задачі Упорядкування всередині інтервалів (УВІ).

Теорема. УВІ - NP-повна в сильному значенні.

Побудуємо псевдополіноміальне зведення задачі З-РОЗБИТТЯ до задачі УВІ.

Нехай - визначає довільну задачу З-РОЗБИТТЯ. Побудуємо індивідуальну задачу УВІ:

Ця зведеність може бути здійснена за поліноміальний час тільки по відношенню до довжини запису вихідної інформації, а довжина індивідуальних задач, які отримані при такому зведенні, поліноміально еквівалентна довжині вихідних задач. Таким чином, умови б) та в) з визначення поліноміального зведення виконуються. Більш того, найбільше число в побудованій задачі дорівнює тВ+т-1, тому виконується також умова г). Доведемо умову а)

В  послідовності завдань, що задовольняє вище переліченим умовам, завдання t₁, 1iB повинно виконуватися в проміжку часу від iB+i-1 до iB+1. При цьому залишається m окремих блоків часу B кожний. Сума часу у всіх блоках дорівнює загальному часу виконання усіх завдань, а отже усі ці блоки повинні бути заповнені повністю. Ці блоки відіграють таку ж роль, що і чисельності S₁, S₂, ..., S_m в пошуковаму розбитті чисельності А. Отже, шукана послідовність існує  коли існує искомое розбиття у вихідній індивідуальній задачі з З-РОЗБИТТЯ. ...