ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2344
Скачиваний: 1
51
6. ТЕОРІЇ СКЛАДНОСТІ ОБЧИСЛЕНЬ І КЛАСИ
СКЛАДНОСТІ ЗАДАЧ
6.1 Теоретична межа трудомісткості завдання
Розглядаючи деяку задачу, що має алгоритми розв'язку, і аналізуючи один
з алгоритмів її вирішення, можна отримати оцінку трудомісткості цього
алгоритму в найгіршому випадку – A (D
A
) = O (g (D
A
)). Такі ж оцінки можна
отримати і для інших відомих алгоритмів вирішення даної задачі. При
дослідженні задачі аналізу алгоритмів виникає питання – а чи існує нижня
межа для g(D
A
) і якщо «так», то чи існує алгоритм, що її вирішує з
трудомісткістю для найгіршого випадку.
Тобто, яка оцінка складності самого «швидкого» алгоритму розв’язку
даної задачі в найгіршому випадку? Очевидно, що це оцінка самої задачі, а не
будь-якого алгоритму її рішення. Таким чином, визначення поняття
теоретичної нижньої межі трудомісткості завдання в найгіршому випадку має
вид:
F
min
= min {
Θ
(F
a
^
(D)) }
Якщо можливо на основі теоретичних міркувань довести існування і
отримати функцію оцінки, то можна стверджувати, що будь-який алгоритм,
який вирішує дану задачу працює не швидше, ніж з оцінкою Fmin в
найгіршому випадку:
F
a
^
(D) =
Ω (F
min
)
Наведемо ряд прикладів:
1)
Задача пошуку максимуму в масиві A = (a
1
, ..., an) –
для цього
завдання, очевидно, повинні бути переглянуті всі елементи і Fmin = Q(n).
2)
Задача множення матриць – для цього завдання можна зробити
припущення, що необхідно виконати деякі арифметичні операції з усіма
вхідними даними, теоретичне обґрунтування якої-небудь іншої оцінки на
сьогодні не відомо [5], що приводить нас до оцінки Fmin = Q(n
2
).
Відзначимо, що кращий алгоритм множення матриць має оцінку Q (n
2
,
34) [6].
Розбіжність між теоретичною межею і оцінкою кращого відомого
алгоритму дозволяє припустити, що або існує, але ще не знайдений більш
швидкий алгоритм множення матриць, або оцінка Q (n
2
, 34
) повинна бути
доведена, як теоретична межа.
52
6.2 Класи складності задач
На початку 1960-х років, у зв'язку з початком широкого використання
обчислювальної техніки для вирішення практичних задач, виникло питання
про межі практичної застосовності даного алгоритму розв'язання задачі в
сенсі обмежень на її розмірність. Які задачі можуть бути вирішені на ПК за
реальний час?
Відповідь на це питання було дано в роботах Кобм (Alan Cobham, 1964), і
Едмондса (Jack Edmonds, 1965), де були введені
класи складності задач.
1)
Клас P (задачі з поліноміальною складністю)
Задача називається поліноміальною, тобто відноситься до класу P, якщо
існує константа k і алгоритм, що вирішує задачу з
F
a
(n) = O (n
k
),
де n – довжина входу алгоритму в бітах n = |D| [5].
Задачі класу P – це задачі, які вирішуються за реальний час.
Відзначимо переваги алгоритмів з цього класу:
•
для більшості задач з класу P константа k менше 6;
•
клас P інваріантний до моделі обчислень (для широкого класу моделей);
•
клас P має властивість природної замкнутості (сума або добуток
поліномів є поліном).
Таким чином, задачі класу P є уточнення визначення «практично
вирішуваної» задачі.
2)
Клас NP (задачі, що перевіряються поліноміально)
Нехай деякий алгоритм дає рішення деякої задачі. Чи відповідає
отримана відповідь поставленій задачі, і на скільки швидко можна перевірити
правильність рішення?
Розглянемо, наприклад, задачу про суму:
Задано N чисел – А = (a
1
, ... an
) і число V.
Треба знайти вектор (масив) X = (x
1
, ..., xn), xi
є {0,1}, такий, що
∑
a
i *
x
i
= V .
Тобто треба визначити, чи може бути представлено число V у вигляді
суми будь-яких елементів масиву А.
53
Якщо деякий алгоритм визначає масив X, то перевірка правильності
цього результату може бути виконана з поліноміальною складністю:
перевірка
∑
a
i *
x
i
= V
вимагає не більше Q (N) операцій.
Формально:
∀
D
∈
D
A
, |D|=n
поставимо у відповідність сертифікат S
∈
S
A
,
такий, що | S | = O (n
l
) і алгоритм As = As (D, S), такий, що він видає « 1 »,
якщо рішення правильно, і «0», якщо рішення невірно.
Тоді задача належить класу NP, якщо F (As) = O (n
m
) [6].
Змістовно задача відноситься до класу NP, якщо її рішення за
допомогою деякого алгоритму може бути швидко (поліноміально) перевірено.
6.3 Проблема P = NP
Після введення в теорію алгоритмів понять класів складності Едмондсом
(Edmonds, 1965
) була сформульована основна проблема теорії складності –
Чи вірно твердження P = NP?
Словесне формулювання проблеми має вигляд: чи можна всі задачі,
вирішення яких перевіряється з поліноміальною складністю, вирішити за
поліноміальний час? [5].
Очевидно, що будь-яка задача, що належить класу P, належить і класу
NP,
оскільки вона може бути поліноміально перевірена – задача перевірки
рішення може складатися просто в повторному рішенні задачі.
На сьогодні відсутні теоретичні докази як збігу цих класів (P = NP), так і
їх неспівпадання.
Припущення полягає в тому, що клас P є власною підмножиною класу
NP,
тобто NP \ P не порожньо – рис 6.1.
Рис 6.1. Співвідношення класів P і NP
P
NP
NP \ P
≠
0
54
6.4
Клас NPC (NP – повні задачі)
Поняття NP – повноти було введено незалежно Куком (Stephen Cook,
1971) і Левіним (журнал «Проблеми передачі інформації», 1973, т. 9, вип. 3) і
ґрунтується на понятті зводимості однієї задачі до іншої [5].
Зводимість може бути представлена наступним чином: якщо ми маємо
задачу 1 і алгоритм, що вирішує цю задачу і видає правильну відповідь для
всіх вхідних даних, що складають задачу, а для задачі 2 алгоритм рішення
невідомий, то, якщо можна переформулювати (звести) задачу 2 в термінах
задачі 1, то можна вирішити задачу 2.
Таким чином, якщо задача 1 задана множиною конкретних проблем D
A1
,
а задача 2 – множиною, і існує функція f
s
(алгоритм), що зводить конкретну
постановку задачі 2 (D
А2
) до конкретної постановки задачі 1 (D
А1
):
f
s
(d
(2)
∈D
A2
) = d
(1)
∈D
A1
,
то задача 2 зводиться до задачі 1.
Якщо при цьому F
A
(f
s
) = O (n
k
), тобто алгоритм зведення належить до
класу P, то говорять, що задача 1 поліноміально зводиться до задачі 2 [5].
Прийнято говорити, що задача задається деякою мовою. Тобто якщо
задача 1 задана мовою L1, а задача 2 – мовою L2, то поліноміальна
зводимість визначається наступним чином:
L2
≤
p
L1.
Визначення класу NPC (NP-complete) або класу NP-повних задач
вимагає виконання наступних двох умов: по-перше, задача має належати
класу
NP (L
∈ NP),
і, по-друге, до неї поліноміально повинні зводитися всі задачі з класу
NP (L
x
≤
P
L,
для кожного L
x
∈ NP),
що схематично представлено на рис 6.2.
55
Рис 6.2. Зводимість NP класу і NPC
Для класу NPC доведена наступна теорема:
Якщо існує задача, що належить класу NPC, для якої існує
поліноміальний алгоритм розв’язку (F = O (n
k
)),
то клас P збігається з класом
NP,
тобто P = NP [5].
Схема доказу полягає у зведенні будь-якої задачі з NP до даної задачі з
класу NPC з поліноміальною трудомісткістю і вирішенні цієї задачі за
поліноміальний час (за умовою теореми).
В даний час доведено існування сотень NP-повних задач [5,6], але ні для
однієї з них поки не вдалося знайти поліноміального алгоритму рішення.
Крім того дослідники припускають наступне співвідношення класів,
показане на рис 6.3.
P
≠ NP,
тобто NP \ P ≠ 0, і задачі з класу NPC не можуть бути вирішені (сьогодні)
з поліноміальною трудомісткістю.
Рис 6.3. Співвідношення класів P, NP, NPC
NP
NPC
NP
P
NPC