Недетерминирани алгоритми и клас NP

Да се ​​въведе сложен и примерен

абстрахирайки понятието за недетерминиран алгоритъм, помислете за една проста схема за решаване на проблема на пътуващия продавач в следната настройка: има ли дадена крайна графика с дадени дължини на дъги хамилтонов контур с дължина, която не надвишава стойността IN.

Ако броят на върховете в графиката е н, тогава броят на всички хамилтонови

очевидно контурите няма да надвишават (n-1)!.

Тривиален изчерпателен алгоритъм за търсене се състои от

2 ° Изберете редовни хамилтонови офиси γ.

3 ° Изчислете дължината му L (γ) .

4 ° Ако, тогава УСПЕХ ? "ВЯРНО"; отидете на 6 °>.

5 ° Ако изброяването на всички хамилтонови контури не е завършено,

6 ° Изходна променлива стойност УСПЕХ.

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

лесно е да се види, че тривиалният алгоритъм не е полиномиален по сложност. Това е типичен пример за т.нар

За да се изгради теория за сложността на решаването на дискретни задачи, беше предложено недетерминиран оператор на отгатване

отделни елементи от изброени множества - осъществими решения,

и се счита; че такъв оператор прави избор от всички възможни решения наведнъж. Тази абстракция отговаря на обичайното

идеята за паралелизиране на алгоритми.

Ако х - е краен набор от възможни решения на някакъв проблем, а след това недетерминираният оператор ИЗБЕРЕТЕ (X) извършва

избор х ? ИЗБЕРЕТЕ (X) всички едновременно xÎX, така че последващи действия

алгоритмична проверка на някакво свойство (предикат) P (x) позволява да се направи извод за неговата осъществимост или невъзможност

на целия комплект наведнъж х. Можем да кажем, че ако елемент със свойства, които ни интересуват в набора х присъства, тогава неопределеният оператор непременно ще „познае“ този елемент. Типично

пример за недетерминиран алгоритъм е:

ако P (x) след това напишете ("УСПЕХ")

еlse writeе ("FAILURE");

Такива алгоритми съдържат два основни елемента;

недетерминиран избор и проверка на свойство. Сложността на недетерминиран алгоритъм се определя само от сложността на проверката на свойството P (x), сложността на изброяването се елиминира от недетерминирания оператор по избор, което е абстракция, която е трудна за възприемане, но най-важна за теорията на сложността

Обикновено модел на недетерминирана алгоритмична система е недетерминирана машина на Тюринг (ЛЕПЕЩО) [един]. но

ще използваме модел, който е по-близо до реалния ход

изчисления на съвременен еднопроцесорен компютър:

алгоритмичен език с добавен недетерминиран

оператор ИЗБИРАМ (). Такъв език ще се нарича N-АЛГОЛ и го считайте за разширение на някакъв алгоритмичен език. високо ниво, условно наречено АЛГОЛ. Програма на езика N-АЛГОЛ ще звънна N-програма. Изпълнение на недетерминиран оператор ИЗБИРАМ () се брои за една елементарна стъпка.

---