Класи складності

У рамках класичної теорії здійснюється класифікація завдач за класами складності (P -складні, NP -складні, експоненціально складні та ін.). До класу P відносяться задачі, які можуть бути вирішені за час, поліноміальний залежний від об'єму початкових даних, за допомогою детермінованої обчислювальної машини (наприклад, машини Т'юринга), а до класу NP — задачі, які можуть бути вирішені за поліноміальний виражений час за допомогою недетермінованої обчислювальної машини, тобто машини, наступний стан якої не завжди однозначно визначається попередніми. Роботу такої машини можна представити як процес, що розгалужується на кожній неоднозначності: задача вважається вирішеною, якщо хоч би одна гілка процесу прийшла до відповіді. Інше визначення класу NP: до класу NP відносяться задачі, рішення яких за допомогою додаткової інформації поліноміальної довжини, ми можемо перевірити за поліноміальний час. Зокрема, до класу NP відносяться усі задачі, рішення яких можна перевірити за поліноміальний час. Клас P міститься в класі NP. Класичним прикладом NP-задачі є завдання про комівояжера.

Оскільки клас P міститься в класі NP, приналежність задачі до класу NP часто відбиває наше поточне уявлення про способи рішення цієї задачі і носить неостаточний характер. У загальному випадку немає підстав вважати, що для NP-задачі не може бути знайдене P-рішення. Питання про можливу еквівалентність класів P і NP (тобто про можливість знаходження P-рішення для будь-якої NP-задачі) вважається одним з основних питань сучасної теорії складності алгоритмів. Відповідь на це питання не знайдена досі. Сама постановка питання про еквівалентність класів P і NP можлива завдяки введенню поняття NP-повних задач. NP-повні задачі складають підмножину NP-задач і відрізняються тією властивістю, що усі NP-задачі можуть бути тим або іншим способом зведені до них. З цього виходить, що якщо для NP-повної задачі буде знайдено P-рішення, то P–рішення буде знайдене для усіх завдань класу NP. Прикладом NP-повної задачі є задача про кон'юнктивну форму.

Дослідження складності алгоритмів дозволили по-новому поглянути на рішення багатьох класичних математичних завдань і знайти для ряду таких завдань (множення многочленів і матриць, рішення лінійних систем рівнянь та ін.) рішення, що вимагають менше ресурсів, ніж традиційні.

Складність завдання і поліноміального сходження

Складнощі завдання характеризують складністю найкращого алгоритму, що вирішує задачу з найважчим значенням входу.

Розрізняють 3 основні класи складності задач :

1) задачі, для яких відомі алгоритми поліноміальної складності;

2) задачі, для яких не відомі алгоритми поліноміальної складності, але для яких і не доведено неіснування таких алгоритмів;

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

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

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

Великою різноманітністю відносної складності відрізняються задачі дискретної математики. Алгоритми рішення багатьох з них мають переборний характер, що часто призводить до важко розв’язаності задач. Нерідкі випадки, коли така задача може бути вирішена тільки шляхом застосування алгоритму повного перебору. У такому разі складність задачі визначається тим, наскільки швидко росте безліч варіантів зі збільшенням розміру вхідних даних.

Сходженість задач

Говорять, що задача Z1 поліноміальний зводиться до задачі Z2, якщо рішення задачі Z1 можна отримати з рішення відповідної задачі Z2 за поліноміальний час.

Відмітимо, що якщо задача Z2 має поліноміальну складність і поліноміальне сходження задачі Z1 до задачі Z2 доведена, то тим самим доведена поліноміальна складність задачі Z1.

Класи задач P і NP

Клас P є безліччю задач, для кожної з яких існує детермінований алгоритм з поліноміальною функцією складності.

Клас NP визначається як безліч задач, які можуть бути вирішені недетермінованим алгоритмом з поліноміальною функцією складності.

Очевидно, що P NP.

NP-складні і NP-повні завдання

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

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

Таким чином, мають місце наступні співвідношення:

{NP-повні} {NP-складні}

складність(NP-повна)≤складність(NP-складна).

Приклад NP-складної задачі: знайти оптимальний маршрут в симетричному завданні комівояжера (тобто з симетричною матрицею вартості).

Приклади NP-повних задач:

- завдання про здійснимість булевого виразу, представленого в КНФ;

- визначити, чи містить заданий граф повний підграф з k –вершинами.