евидно. Ми повинні перевірити протокол деякої НМТ, працюючої за поліноміальний час. Це займе нас приблизно на той же час (зовсім нема чого дивитися на одну клітинку експоненціально довго). p> Опр. 2.2 опр. 2.1. Нехай є з визначення 2.2. Побудуємо для визначення 2.1. Вона працює в два етапи. p> Спочатку недетермінірованного пише (який в силу визначення 2.2 існує для будь-якого слова, для якого). Кажуть ще, що "відгадує" ("guesses"). Більш точно це означає, що знаходить правий кінець вхідного слова, зсувається ще на одну клітинку вправо, записує в неї, ще раз зсувається вправо і переходить в таке недетермінірованного стан, в якому вона пише один із символів на стрічку, зсувається вправо і вибирає між збереженням цього стану і переходом у (вже детерміноване) стан початку наступного етапу.
Після завершення першого етапу на стрічці, крім вхідного слова, записано ще й слово. Тепер залишилося обчислити значення предиката за поліноміальний час. Це можна зробити, використовуючи детермінований алгоритм, який існує в силу визначення 2.2. p> Ще одне визначення класу NP є не більше ніж варіант визначення 2.2, але саме в такій формі його зручно узагальнювати і отримувати визначення інших сложностних класів.
Визначення 2.3. Є два персонажі: король A rthur (Артур), розумові здібності якого полиномиально обмежені, і чарівник M erlin (Мерлін), який інтелектуально всемогутній і знає правильні відповіді на всі питання. Король A цікавиться деякими властивістю (наприклад, "чи є у графа гамільтонів цикл"), а чарівник M хоче, щоб король визнав наявність цієї властивості (ну, скажімо, граф прагне до звання гамільтонового і дав M хабар). A не довіряє своєму чарівникові, знаючи його користолюбство, і хоче мати можливість самостійно перевірити запропонований M відповідь. p> Тому вони діють наступним чином. A і M обидва дивляться на слово, після чого M повідомляє деяку інформацію (слово), яка повинна переконати A, що. Використовуючи цю інформацію, A перевіряє переконливість аргументів M деяким поліноміальним способом. p> У цих термінах визначення класу NP можна сформулювати так: властивість належить класу NP, якщо у Артура є поліноміальний спосіб перевіряти переконливість доводів Мерліна, причому:
у M є спосіб переконати A в цьому;
як би M ні витончувався, A не повірить, що.
Еквівалентність цього визначення визначенню 2.2 не викликає сумнівів. Дійсно, через поліноміальної обмеженості короля A, повідомлення чарівника M повинно мати поліноміальний розмір. У іншому відмінності між визначеннями суто зовнішні. br/>
Тема 2.2 сводимости і NP-повнота
Складність обчислення предикатів можна порівнювати, користуючись наступним визначенням.
Визначення 2.4. Сводімость по Карпу. Предикат зводиться до предикату (позначення ), якщо існує така функція
