Асимптотические представлення

Складність алгоритму

Довжина слова, що кодує задачу I, – це величина n, функцією від якої визначається складність алгоритму А.

Визначення. Під складністю алгоритму надалі розуміється його тимчасова складність, тобто функція f (n), що кожній довжині n вхідного слова (коду задачі) ставить у відповідність максимальне (по всіх індивідуальних задачах довжини n) число елементарних дій, затрачуване алгоритмом у процесі рішення задач цієї довжини.

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

Дуже часто, щоб порівняти одну величину з інший, досить знать не точні, а наближені значення. У таких випадках звичайно записують: A» B (A приблизно дорівнює B). Для оперирования наближеними величинами в математику прийнято використовувати символ O, що дає можливість заміняти символ» символом =. Запис O(f(n)) застосовується тоді, коли f(n) є функцією від цілого позитивного n, однак точне значення цієї функції невідомо, – відомо лише, що значення це невелико. Більш точно, запис O(f(n)) означає, що існує позитивна константа з, така, що величина x_n, представлена як O(f(n)), задовольняє умові:

| x_n | £ c | f (n)| для всіх n ³ 0.

Наприклад, співвідношення H_n = ln(n) + v + O(1/n) означає, що | H_n – ln(n) + v | £ c/n. Константа з невідома, однак, зрозуміло, що O(1/n) буде як завгодно мало, якщо n досить велико.

Символ O завжди коштує в правій частині рівності. Наприклад, n^2/2 + n = O(n²) означає, що n^2/2 + n не більше, ніж n², тобто при досить великому n значення вираження n^2/2 + n будить приблизно дорівнює n². Якщо це оцінка складності алгоритму, то можна сказати, що складність алгоритму квадратична.

Для O(f(n)) здійсненні наступні властивості:

f(n) = O(f(n)),

cO(f(n)) = O(f(n)),

O(f(n)) + O(f(n)) = O(f(n)),

O(O(f(n))) = O(f(n)),

O(f(n)) O(g(n)) = O(f(n)g(n)),

O(f(n)g(n)) = f(n)O(g(n)).

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

Запис f (n) ~ O(g (n)) означає, що існує константа з, така, що | f (n)| £ c | g (n)| для всіх n ³ 0. Алгоритм називається поліноміальним, якщо його складність T_A (n) ~ O(p (n)), де p (n) - поліноміальна функція.

Приклад неполіноміальної функції - n ^{log n} .

Складність моделювання машиною B роботи алгоритму складності f (n) на машині А.

Моделируемая	Моделююча машина А
машина B	1МТ	kМТ	МДП
1-стрічкова МТ (1МТ)	-	O(f (n))	O(f (n))log f (n)
k-стрічкова МТ (kМТ)	O(f ^2(n))	-	O(f (n))log f (n)
Машина довільного доступу (МДП)	O(f ^3(n))	O(f ^2(n))	-

Приклад - розпізнавання паліндрома (слова, симетричного щодо середини): на 1-МТ його складність O(n²), а вже на 2-МТ - O(n).

Цю таблицю можна розглядати як виправдання (обґрунтування розумності) усієї наступної теорії. Для будь-якої функції складності:

* аддитивной константою можна зневажити – це, як правило, накладні витрати, помітні лише на задачах малого обсягу;

* мультиплікативна константа переборюється зростаючою швидкодією комп'ютерів;

* ступінь полінома, як видно з таблиці, для однієї і тієї ж задачі може бути різної при різних архитектурах машин; тому, якщо будувати машинно-незалежну теорію складності, ступенем полінома приходиться зневажити. Таким чином, мовчазно приймається теза: перенос задачі на детерминированную машину будь-якої мислимої архітектури змінює її складність не більш ніж полиномиально. У термінах, що вводяться нижче, це означає, що приналежність (або неприналежність) задачі класові P не залежить від типу машини, на якій написаний алгоритм рішення задачі. Тому -

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

Ідея полиномиальности (точніше - розгляд складності з точністю до полиномиальности) - перший ключовий момент теорії. Надалі для зручності формулювань розглядаються тільки задачі розпізнавання властивостей, тобто задачі, рішення яких - це відповідь «так» або «ні». Задача розпізнавання G характеризується двома безлічами: безліччю D_G всіх індивідуальних задач і безліччю індивідуальних задач Y_G з відповіддю «так». При розумних схемах кодування S задача розпізнавання G перетворюється в задачу розпізнавання мови L (G, S) в алфавіті K схеми кодування: L(G, S) ={безліч усіх a ÎK^* , що є кодами задач з Y_G при схемі кодування S. Природно вважати, що коди однієї і тієї ж задачі при різних розумних схемах кодування розрізняються по довжині не більш, ніж полиномиально. «Розумні схеми кодування» - це схеми стиснуті і полиномиально декодируемые.

Детерминированная (тобто звичайна) машина Тьюринга (ДМТ) із двома заключними станами: q («так») і q («ні»).

Мова L_M розпізнається ДМТ M, якщо L_M = { a ÎK^*: M (a) = q }.

Якщо M зупиняється на усіх a ÎK^*, то тимчасова складність T_M (n) визначається так:

T_M (n) = max T_M (a) по усім a таким, що |a| = n.

ДМТ M називається поліноміальної, якщо існує такий поліном p (n), що для будь-яких n T_M (n) £ p (n).

Клас мов P - це безліч усіх мов, для яких існують распознающие їхній ДМТ.

Задача розпізнавання G належить класові P при кодуванні S, якщо L (G, S)Î P.

Задача комівояжера формулюється як задача розпізнавання в такий спосіб:

Чи існує шлях, що проходить через усі міста, довжина якого не перевершує B?

Поліноміальне рішення цієї задачі невідомо. Однак перевірка пред'явленого рішення полиномиальна. Аналогічною властивістю - поліноміальної проверяемостью - володіє задача про ізоморфізм подграфу (у рішення входить указівка конкретної функції, що відображає графа в подграф). Таким чином, з поліноміальної проверяемости не випливає поліноміальна можливість розв'язання.

Недетерминированный «алгоритм»: недетерминированное угадування + поліноміальна детерминированная перевірка.

Недетерминированная машина Тьюринга (НДТМ) містить звичайний детерминированный блок і модуль, що угадує. Обчислення при даному вхідному слові a складається з двох етапів. Спочатку угадує модуль пише на стрічці довільне слово bÎ K^* ліворуч від вхідного слова, а потім детерминированный блок перевіряє, чи не є (рішенням, і переходить або в q, або в q. Таким чином, існує нескінченна безліч різних обчислень при даному вхідному слові a.

НДТМ М приймає a, якщо хоча б одне з обчислень на вході a є приймаючої, тобто переводить М в q.

Мова L_M, розпізнаваний М, - це безліч усіх слів у K^*, прийнятих М.

Час прийняття a T_M (a) = min числа кроків по всіх приймаючих обчисленнях a.

Тимчасова складність М T_M (n) = max T_M (a) по усім a таким, що |a| = n.

T_M (n) = 1, якщо немає жодного слова довжини n, прийнятого М.

Клас NP - це безліч усіх мов, прийнятих НД-машинами за поліноміальний час. Очевидно, що P Í NP.

Теорема. Якщо G Í NP, то існує такий поліном p, що G може бути вирішена детерминированным алгоритмом з тимчасовою складністю O(2 ^{p (n)} ).

Дійсно, нехай q (n) - поліном, що обмежує тимчасову складність НД-алгоритма, що вирішує задачу G. Тоді існує слово-здогад довжини £ q (n), що детерминированно перевіряється за час q (n). Загальне число здогадів не перевершує k ^{q (n)}, де k - потужність алфавіту. Тому час роботи детерминированного алгоритму не перевершує q (n)× k ^{q (n)}. ð

Мова L ₁ полиномиально зводимо до мови L ₂, якщо існує функція f, що задовольняє двом умовам:

1) f має поліноміальну складність;

2) для кожного a aÎ L ₁, якщо і тільки якщо f (a)Î L ₂.

Позначення: L ₁ µ L ₂.

Теорема. Якщо L ₁ µ L ₂, то з L ₂ Î P випливає, що L ₁ Î P. Еквівалентне формулювання: з L ₁ Ï P випливає, що L ₂ Ï P.

Доказ очевидний.

Зведення задачі G₁ до задачі G₂ означає, що G₂ не простіше, ніж G₁.

Це зрозуміло: адже легку задачу можна звести до важкого, а важку до легкого - немає: якщо «важка» зведена до легкого, виходить, вона не така вуж важка.

Приклад. Зведення задачі про існування гамильтонова циклу до задачі про комівояжера.

Нехай в індивідуальній задачі про гамильтоновом цикл G = (V, E), ï V ï= m.

Відповідна задача про комівояжера будується так:

d (v_i, v_j) = 1, якщо (v_i, v_j)Î E, і 2 у противному випадку; B = m.

Функція f, що здійснює це зведення, полиномиальна, оскільки обчислення d (v_i, v_j) зводиться до з'ясування входження (v_i, v_j) у E; усього таких з'ясувань m (m - 1)/2.

Якщо G містить гамильтонов цикл, то цей цикл є маршрутом у f (G) з довжиною m. Він мінімальний, тому що усі ваги на ребрах цього маршруту рівні 1. Отже, у цьому випадку задача f (G) дає позитивну відповідь. Якщо ж G не містить гамильтонов цикл, то довжина мінімального маршруту в f (G) більше m, і відповідь у задачі f (G) - негативний. ÿ

Теорема. Відношення (транзитивно.

Доказ тривіальний. ÿ

Мови L ₁ і L ₂ полиномиально еквівалентні, якщо L ₁ µ L ₂ і L ₂µ L ₁. Це дійсне відношення еквівалентності: воно симетрично по визначенню, а транзитивність µ тільки що доведена. Виникають класи еквівалентності, причому P - найменший клас.

Мова L називається NP-повним, якщо L Î NP і будь-яка інша мова L ’Î NP зводиться до L. Тим самим NP-повні задачі - самі важкі в класі NP, і якщо хоча б одна NP-повна задача утримується в P, те і всі NP-повні задачі утримуються в P.

Помітимо, що в цьому випадку всі задачі з NP утворювали б єдиний клас поліноміальної еквівалентності.

Теорема. Якщо L ₁, L ₂ Î NP, L ₁ - NP-повний і L ₁ µ L ₂, то L ₂ - також NP-повний.

Дійсно, по визначенню, для будь-якого L ’Î NP L’ µ L ₁ і, отже, у силу транзитивності відносини поліноміального зведення L ’ µ L ₂. ÿ

Теорема Кука. Задача выполнимости конъюнктивной нормальної форми є NP-повною. 

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

Є 6 змістовно цікавих задач, NP-повнота яких доводиться зведенням до задачі Кука:

1. 3-выполнимость - выполнимость для КНФ, до якої кожна диз'юнкція містить рівно 3 литерала.

2. Верхове покриття - чи мається в графі G(V, E) верхове покриття не більш ніж з k елементів, тобто таке V¢ Í V, що ½V¢½£ k і хоча б один кінець будь-якого ребра належить V¢?

3. Кліка - чи вірно, що граф містить кліку потужності ³ k?

4. Гамильтонов цикл.

5. k-раскрашиваемость - чи можна розфарбувати граф G(V, E) у k квітів, де k <½V½?

6. Ізоморфізм подграфу.

Усього ж у даний час відомо кілька сотень NP-повних задач з теорій графів, граматик, автоматів і т.д. Для усіх них NP-повнота доводиться зведенням до якої-небудь іншої NP-повної задачі. Таким чином, задача Кука - очевидно, єдина задача, NP-повнота якої доведена прямо, без зведення.

Дата добавления: 2014-01-07