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

 

Чтобы ввести сложное и являющееся примером исключительной

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

Если число вершин графа равно n, то число всех гамильтоновых

контуров, очевидно, не превысит (п-1)!.

Тривиальный алгоритм, основанный на полной переборе состоит в

следующем.

1° УСПЕХ › «FALSE»,

2° Выбрать очередной гамильтонов контор γ.

3° Вычислить его длину L(γ).

4° Если , то { УСПЕХ › «ТRUE»; перейти на 6°}.

5° Если перебор всех гамильтоновых контуров не закончен,

перейти на 2°.

6° Вывод значения переменной УСПЕХ.

 

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

легко убедиться, что тривиальный алгоритм не является полиномиальным по сложности. Это типичный пример так называемого

переборного алгоритма.

Для того, чтобы построить теорию сложности решения дискретных задач, был предложен недетерминированный оператор «угадывания»

отдельных элементов перебираемых множеств - допустимых решений,

причем считается; что такай оператор, осуществляет выбор сразу всех возможных решений. Такая абстракция соответствует обычному

представлению о распараллеливании алгоритмов.

Если Х - конечное множество допустимых решений некоторой задачи, то недетерминированный оператор CHOOSE(Х) осуществляет

выбор х › CHOOSE(Х) одновременно всех хÎХ, так что последующая

алгоритмическая проверка некоторого свойства (предиката) Р(х) позволяет сделать вывод о его выполнимости или невыполнимости

сразу на всем множестве X. Можно сказать, что если элемент с ин-тересующими нас свойствами во множестве Х имеется, то недетерми-нированный оператор обязательно «угадает» этот элемент. Типичный

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

х › СНОOSЕ (Х); {недетерминированный выбор}

if Р(х) then write («УСПЕХ») {проверка свойства}

еlse writе («НЕУДАЧА»);

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

недетерминированный выбор и проверку свойства. Сложность недетерминированного алгоритма определяется только сложностью проверки свойства Р(х), сложность же перебора элиминируется недетерминированным оператором выбора, что и является трудно воспринимаемой абстракцией, но важнейшим для теории сложности

обстоятельством.

Обычно моделью недетерминированной алгоритмической системы является недетерминированная машина Тьюринга (НДТМ) [1]. Однако

мы будем использовать модель, более близкую к реальному ходу

вычислений на современном однопроцессорном компьютере:

алгоритмический язык, к которому добавлен недетерминированный

оператор СНOOSЕ (). Такой язык будем называть N-ALGOL и считать его расширением некоторого алгоритмического языка. высокого уровня, условно названного ALGOL. Программу на языке N-ALGOL будем называть N-программой. Выполнение недетерминированного оператора СНООSЕ () считается одним элементарным шагом.

Определение 3.1. Классом NР называется множество всех задач, для которых существует программа на языке N-ALGOL с полиномиальной временной сложностью, вычисляющая правильный ответ для любых допустимых вариантов исходных данных.

Поскольку язык N-ALGOL является расширением языка ALGOL, то любая программа является N-программой, и выполняется включение

рÌ nр. Справедливость равенства Р = nр сомнительна, поскольку оно повлекло бы существование полиномиальных алгоритмов для всех переборных задач. Поэтому соотношение Р¹ NР, подтверждаемое опытом математиков - вычислителей и специалистов в области теории алгоритмов и математической логики, считается гипотезой.

 

Класс NР - полных задач

Ниже излагаются основы теории сложности, заложенной в основополагающих работах С. Кука [7], Р. Карпа [8], А.А. Левина [9]. Важно обратить внимание на полиномиальное преобразование задач как главный элемент этой теории. Известно, например, что задача о максимальном потоке в сети может быть преобразована в задачу линейного программирования. Подобные преобразования задач иногда оказываются полезными для нахождения решений, и для их осуществления приходится производить некоторые вычисления, связанные с перекодированием начальной информации и

ответа - решения задачи (рис. 4.1).

Определение 4.1. Задачи множества Z полиномиально сводимы к задачам множества S (обозначение - Zµ S), если существует функция j. вычисляемая за полиномиальное время и преобразующая любую задачу zÎ Z в задачу j(z) = s, sÎ S, причем zÎ Z • j(z)Î S

 

	Преобразо-вание за полиноми- альнов время		Алгоритм решения задачи j(z)
			Преобразо-вание за полиноми- альнов время

Вход Вход Выход Выход

задачи задачи задачи задачи

Z j(z) j(z) Z

 

Рис. 4.3. Схема полиномиальной сводимости задачи Z к

задаче j(z).

 

Определение 4.2. Задача Z* называется NР - полной (универсальной переборной задачей), если Z*Î NР и для любой задачи ZÎ NР имеет место полиномиальная сводимость Z µ Z*.

Множество всех NР- полных задач часто обозначают NPС (Nondeterministic Polinoyal Compete). Из определения 4.2. следует, что NPСÌ NP и NP-полные задачи являются наиболее сложными в классе NP: если хотя бы одну NP-полную задачу удалось решить за полино-миальное время, то и все задачи из NP (в силу полиномиальной своди-мости Z µ Z*) также удалось бы решить за полиномиальное время.

Теорема 4.1 [1].

1)Если µ , то Î Р Þ Î Р;

2) Если µ и µ , то µ

3) Если Î NР, Î NР, Î NРС и µ , то Î NРС. Доказательство вытекает из определений 2.1, 3.1, 4.1 и 4.2.

Теорема 4.1 указывает способ доказательства. NР-полноты некоторой задачи Z, если известна хотя он одна NР -полная задача

Z*: достаточно доказать, что Î NР и что Z*µ Z.

Изучение сложности дискретных задач началось с исследования задач вычисления (или распознавания) свойств. Эти задачи для допустимой начальной информации могут иметь решение, представ-ляющее собой ответ «да» или «нет» (1 или 0). Например, имеет ли данный конечный граф хотя бы один гамильтонов контур, является ли совместной система линейных неравенств с целочисленными переменными и тому подобные задачи. В последствии результаты исследования сложности задач вычисления свойств были распространены и на другие, в частности оптимизационные задачи.

Рис.4.2 Теоретико - множественная диаграмма класса NP в предположении

что P¹ NP.