Недетерміновані машини Тюрінга. Np-повні задачі.

§1. NP-повні задачі.

Скільки обчислень повинна вимагати задача, щоб вона вважалася дійсно важкою? Загально прийнято, що коли задачу неможна розв’язати швидше, ніж за експоненціальний час, то її потрібно розглядати як безумовно важко розв’язною. У цій “схемі класифікації“ задачі, котрі розв’язуються алгоритмами поліноміальної складності, будуть легко розв’язні. Проте потрібно мати на увазі, що, хоч експоненціальна функція (така, як 2ⁿ ) зростає швидше будь-якої поліноміальної функції від n, для невеликих значено n алгоритм, який вимагає часу може бути ефективнішим багатьох алгоритмів з поліноміально обмеженим часом роботи. Наприклад, сама функція 2ⁿ не перебільшує для n=59. Проте швидкість зростання експоненціальної функції настільки значна, що ми називатимемо задачу важко розв’язною, якщо у всіх алгоритмі, які її розв’язують, складність щонайменше експоненціальна.

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

§2. Недетерміновані машини Тюрінга

Ключове поняття в теорії NP- повних задач – недетермінована машини Тюрінга (НМТ). НМТ має скінчене число можливих кроків, із яких у наступний момент вибирається якийсь один. Вхідний ланцюг х допускається, якщо принаймні одна послідовність кроків для входу х приводить до миттєвого опису (МО), який допускається.

При заданому вхідному ланцюгу х можна вважати, що НМТ М паралельно виконує всі можливі послідовності кроків, поки не досягне МО, який допускається або не виявиться, що подальші кроки неможливі. Іншими словами, після і кроків можна вважати, що існує багато екземплярів М. Кожен екземпляр представляє МО, в якому М може виявитися після і кроків. На (і+1)-му кроці екземпляр С породжує j своїх екземплярів, якщо МТ, знаходячись в МО С, може вибрати наступний крок j способами.

Таким чином, можливі послідовності кроків машини М на вході х можна організувати у вигляді дерева миттєвих описів. Кожний шлях із кореня до листка цього дерева представляє деяку послідовністю можливих кроків. Якщо σ – найкоротша послідовність кроків, яка закінчується МО, який допускається, то як тільки машина зробить |σ| кроків, вона зупиниться й допустить вхід х. Час, який витрачається на обробку входу х, дорівнює довжині послідовності σ. Якщо на вході х жодна послідовність кроків не приводить до МО, який допускається, то М відкидає х, а час, витрачений на обробку х, не визначений.

Часто зручно уявляти собі, що М “вгадує“ тільки кроки із послідовності σ й перевіряє, що σ насправді закінчується МО, який допускається. Але оскільки детермінована машина зазвичай не може заздалегідь вгадати послідовність кроків, які допускаються, то де терміноване моделювання машини М вимагало б перегляду в деякому порядку дерева всіх можливих послідовностей кроків на вході х і цей перегляд продовжувався б до виявлення найкоротшої послідовності, котра закінчується МО, який допускається. Якщо ніяка послідовність кроків не приводить до допущення входу, то детерміноване моделювання машини М могло б продовжуватися нескінченно довго, якщо тільки немає якої-небудь апріорної межі на довжину найкоротшої послідовності, котра допускається. Тому природно очікувати, що не детерміновані МТ здатні виконувати завдання, котрі ніякі детерміновані МТ не можуть виконати за той же час або з тією ж пам’яттю. Тим не менше, все ще відкрите важливе питання про існування мов, які допускаються недетермінованою МТ з даною часовою або ємнісною складність, але не допускаються жодною детермінованою МТ з тією ж складністю.

Визначення 1. k- стрічковою недетермінованою машиною Тюрінга (НМТ) М називають семірку (Q, T, I, δ, b, , ) де значення всіх компонент ті ж, що й для звичайної детермінованої МТ, за виключенням того, що тут фіксація переходів δ є відображенням множини в множину підмножин в . (L означає зсув голівки вліво, R – вправо, S – голівка залишається на місці).Іншими словами, за даним станом і списком із k стрічкових символів функція δ видає скінчену множину варіантів наступного кроку; кожен варіант складається з нового стану, k нових стрічкових символів і k зсувів голівки. Зазначимо, що НМТ М може вибирати довільний з цих варіантів кроків, але не може вибирати наступний стан із одного кроку, а нові стрічкові символи – з другого або створити яку-небудь ще комбінацію варіантів кроків.

Миттєвий опис для НМТ визначається точно так же, як і для детермінованої МТ (ДМТ). Дана НМТ М=(Q, T, I, δ, b, , ) робить крок, виходячи зі свого стану, скажемо q, і символів, які оглядає кожна із k голівок, скажемо . Із множини вона вибирає деякий елемент . Цей елемент показує, що новим станом повинно стати r, на і-тій стрічці потрібно надрукувати замість й зсунути голівку в напрямку, який позначається символом , . Якщо при деякому виборі наступного кроку МО переходить в МО D, то пишуть С |– _МD (або С |–D, якщо зрозуміло, про яку машину М йде мова). Зазначимо, що для даної НМТ М може бути декілька таких D, що С |–D, але якщо машина М детермінована, то для кожного С існує не більше одного такого D.

Запис С₁ |–* означає, що для деякого k виконується

С₁ |– С₂ |– … |– |С_k= ,

або С₁ = . НМТ М допускає ланцюг w, якщо

|–* ,

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

Приклад 1. Побудуємо НМТ, яка допускає такі ланцюги вигляду

,

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

Побудуємо трьох стрічкову НМТ М, яка розпізнає цю мову. Вона переглядає свою вхідну стрічку зліва направо, і кожного разу, коли вона доходить до блоку вигляду , на другу або третю стрічку добавляються ці нулів, причому вибір стрічки не детермінований. Після того як машина дійде до кінця входу, вона перевірить, чи збігається число нулів на стрічках 2 і 3, і, якщо так, допустить вхід. Тому, якщо яка-небудь послідовність виборів, котра вказує, в яку із множин поміщати наступне число – в першу (на стрічку 2) чи в другу (на стрічку 3), приводить до рівних сум, то ця НМТ допускає вхід. Послідовність кроків, які приводять до нерівних ланцюгів на стрічках 2 і 3 не беруться до уваги, якщо принаймні одна послідовність виборів спрацьовує. Формально нехай

,

Де функція переходів задана на рис.1.

На рис. 2 показані дві з багатьох послідовностей кроків, які може зробити на вході 1010010 ця НМТ. Перша приводить до стану, який допускається, а друга ні. Оскільки принаймні одна послідовність кроків приводить до стану, який допускається, ця машина приймає 1010010.

Стан	Поточний символ на стрічці				Новий символ, зсув голівки на стрічці			Новий стан	Зауваження
	1		2	3	1	2	3
	1	B		B	1, S	S, R	S. R		Машина відмічає ліві кінців стрічок 2 і 3 знаком S і переходить в стан
	1	B		B		b, S b, S	b, S b, S		Тут машина вибирає, писати наступний блок на стрічці 2 ( ) або 5 ( )
	0 1 b	b b b		B b b	0, R 1. S b, S	0, R b, S b, L	b, S b, S b. L		Машина переписує блок із нулів на стрічку 2, потім по досягненню одиниці на стрічці 1 повертається в стан . Якщо ж на стрічці 1 досягнуто символ b, вона переходить в стан , щоб порівняти довжини стрічок 2 і 3.
	0 1 b	b b b		B b b	0, R 1. S b, S	b, S b, S b, L	0, R b, S b, L		Те ж саме, що в стані , але запис на стрічку 3
	b b	0 S		0 S	b, S b, S	0, L S, S	0, L S, S		Порівняння довжин стрічок 2 і 3.
									Машина допускає вхід.

Рис. 1. Кроки НМТ. Кожен рядок є одним варіантом вибору.

_______________________________________________________________

( 1010010, , ) ( 1010010, , )

|– ( 1010010, S , S ) |– ( 1010010, S , S )

|– (1 010010, S , S ) |– (1 010010, S , S )

|– (10 10010, S0 , S ) |– (10 10010, S , S0 )

|– (10 10010, S0 , S ) |– (10 10010, S , S0 )

|– (101 0010, S0 , S ) |– (101 0010, S , S0 )

|– (1010 010, S0 , S0 ) |– (1010 010, S , S00 )

|– (10100 10, S0 , S00 ) |– (10100 10, S , S000 )

|– (10100 10, S0 , S00 ) |– (10100 10, S , S000 )

|– (101001 0, S0 , S00 ) |– (101001 0, S , S000 )

|– (1010010 S00 S00 ) 11 |– (1010010 , S , S0000 )

|– (1010010 , S0 0, S0 0) |– (1010010 , S, S000 0)

|– (1010010 , S 00, S 00) Зупинка – немає наступного МО.

|– (1010010 , S00, S00)

|– (1010010 , S00, S00)

Вхід допускається.

Рис 2. Дві можливі послідовності кроків для НМТ.

Визначення 2. Говорять, що НМТ М має часову складність , якщо для будь-якого вхідного допустимого ланцюга довжиною n знайдеться послідовність, котра складається не більше ніж кроків, котра приводить в допустимий стан, і ємнісну складність , якщо для будь-якого допустимого ланцюга довжиною n знайдеться послідовність кроків, котра приводить в допустимий стан, в якому число переглянутих голівкою клітинок на кожній стрічці не перевищує .

Приклад 2. НМТ із прикладу 1 має часову складність (найгірший випадок – вхід із n одиниць) і ємнісну складність .