2. Клас NP: сводімость і повнота
Тема 2.1 Клас NP
Термін "недетермінірованний" невдалий, але він вже став стандартним.
Клас NP визначений тільки для предикатів. Кажуть, наприклад, що "властивість графа" мати гамільтонів цікл1) <# "16" src = "doc_zip497.jpg"/> належить класу, якщо існують НМТ і поліном такі, що
існує шлях обчислення, що дає відповідь "так" за час, що не перевершує;
(1 варіант визначення) немає зазначеного вище шляху; (2 варіант визначення) на будь-якому шляху обчислення відповіді "так" не виходить.
Зауваження 2.1. Наведені варіанти визначення еквівалентні. Щоб виключити можливість відповідей "так" на довгих шляхах обчислення, достатньо взяти НМТ, що імітує вихідну НМТ і підраховують кількість зроблених вихідної НМТ кроків. Коли число кроків перевищує, машина зупиняється. p> Зауваження 2.2. У попередньому міркуванні допущена одна тонка помилка. У визначенні нічого не сказано про поліномі, окрім факту його існування. Якщо коефіцієнти полінома невичісліми, можуть виникнути проблеми з зазначеним вище способом відомості одного визначення до іншому (потрібно обчислити значення полінома). Щоб надалі уникати цієї складності, будемо вважати, що поліном має цілі коефіцієнти. p> Зауваження 2.3. Безпосередньо з визначення 2.1 треба, що. Чи є це включення суворим? Досить інтенсивні, хоча й безуспішні, спроби відповісти на це питання тривають вже майже 30 років. Нещодавно С.Смейл включив проблему до числа трьох найважливіших математичних проблем наступного століття (дві інші - гіпотеза Рімана і гіпотеза Пуанкаре). p> Друге визначення класу NP видається більш природним. Воно використовує поняття полиномиально вичіслімого предиката від двох змінних. Визначення такого предиката виходить комбінацією визначень 1.2 і 1.3. Під розміром входу для предиката можна розуміти також або, або - вийдуть еквівалентні визначення. p> Визначення 2.2. Предикат належить класу NP, якщо він представимо у формі, де - поліном, а. p> Приклад 2.1. Нехай "є гамільтонів цикл в графі". Більш точно потрібно сказати так: "є двійковий код деякого графа, а - код Гамільтона циклу в цьому графі (використовуємо таке кодування, при якому код циклу не довше коду графа), такі що". Візьмемо. Тоді буде в точності означати, що в графі знайдеться гамільтонів цикл. p> Теорема 2.1. Визначення 2.1 і 2.2 еквівалентні. p> Опр. 2.1 опр. 2.2. Нехай є НМТ і поліном з першого визначення. Розглянемо предикат "є протокол роботи на можливому шляху обчислення зі входом дає відповідь" так "за час, що не перевершує." Довжина такого протоколу при розумному кодуванні лінійно залежить від часу обчислення (якщо використовувати в якості протоколу описану в доведенні теореми 1.2 таблицю обчислення, то квадратично), тому в якості для другого визначення можна взяти (), помножений на відповідну константу.
Щоб закінчити доказ в цьому випадку, залишилося перевірити, що. Це майже оч...
