Недетерминированный алгоритм

Cтраница 2

По существу в доказательстве дается процедура построения, которая для любого полиномиального недетерминированного алгоритма, выходом которого будет просто истинно или ложно, и для любой входной последовательности строит одно булево выражение в конъюнктивной нормальной форме, которое является выполнимым, если и только если для этой входной последовательности алгоритм вычисляет ответ истинно. Далее, в доказательстве показывается, что построение этого булевого выражения из формального описания недетерминированного алгоритма и его входной последовательности можно выполнить за полиномиальное время. Опираясь на этот результат, можно показать, что существует последовательность таких булевых выражений, соответствующая разрядам выходной последовательности для любого алгоритма из оЛГ 3 и любой входной последовательности. [16]

Прежде чем рассматривать различные другие оЛГ - полные задачи, обсудим некоторое аномальное свойство недетерминированных алгоритмов. Рассмотрим задачи разрешения, ответами в которых являются просто да или нет ( например, Является ли это булево выражение выполнимым. Является ли это булево выражение невыполнимым. Если существует детерминированный полиномиальный алгоритм для Р, то простым отрицанием выхода мы получаем детерминированный полиномиальный алгоритм для дополнения Р; таким образом, Р Р, если и только если Р У. Для оЛГ5 такой результат не известен. [17]

Казалось бы, предыдущее обсуждение делает смешной саму постановку вопроса, совпадает ли класс Р с классом NP. Пример с задачей сортировки, которая решается как полиномиальным детерминированным, так и полиномиальным недетерминированным алгоритмом, подтверждает, что класс Р является подклассом в NP. [18]

Одно соотношение заключается в том, что Р с NP. Всякая задача распознавания, разрешимая за полиномиальное врем детерминированным алгоритмом, разрешима также за полиномиальное время недетерминированным алгоритмом. Чтобы убедиться в этом, достаточно заметить, что любой детерминированный алгоритм может быть использован в качестве стадии проверки недетерминированного алгоритма. Если II Р и А - произвольный детерминированный алгоритм решения задачи II, то полиномиальный недетерминированный алгоритм для II можно получить, воспользовавшись А в качестве стадии проверки и игнорируя стадию угадывания. [19]

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

Большое число важных вычислительных проблем, для которых неизвестно, принадлежат ли они Р, очевидно, принадлежит NP. Например, проблема определения: могут ли вершины графа G быть раскрашены красками таким образом, что никакие две соседние вершины не имеют одинакового цвета. Недетерминированный алгоритм может просто наугад задать цвета вершин и затем - пров - рить ( за полиномиальное время), имеют ли все пары соседних вершин различный цвет. [21]

Этот метод, если он применен неправильно, может дать в результате экспоненциальное увеличение длины формулы. Здесь мы совместим его применение с недетерминированным алгоритмом таким образом, что кванторы элиминируются по мере перемещения к своим областям действия. [22]

В такой системе нормативов преобразуются входные данные в выходные на каждом уровне и при переходе с одного уровня на другой, это преобразование может быть динамическим с заданным детерминированным алгоритмом и последовательно выполняемыми операциями. Это характерно для функционирования непрерывных производств системы газоснабжения. Кроме того, преобразование данных может быть с недетерминированным алгоритмом. При этом совокупность операций может выполняться в разное время и в разной последовательности. Это характерно для процессов сооружения объектов. [23]

Чтобы понять, какие следствия будут вытекать из того, что Р содержит задачу коммивояжера или одну из многих других загадочных задач, необходимо ввести класс № У задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма. Не формально мы определяем состояние алгоритма как комбинацию адреса выполняемой в текущий момент команды и значений всех переменных. Другими словами, детерминированный алгоритм в каждый момент времени может делать только что-то одно. В недетерминированном алгоритме для любого данного состояния может быть больше одного допустимого следующего состояния; другими словами, недетерминированный алгоритм в каждый момент времени может делать больше одной вещи. Недетерминированные алгоритмы не являются в каком-либо смысле вероятностными или случайными алгоритмами; они являются алгоритмами, которые могут находиться одновременно во многих состояниях. [25]

Имеются простые ситуации, где применение рамок может дать хороший результат. Это приводит нас ко второму частному решению - рассматривать только такие простые модели мира, для которых адекватен метод приписываний. В настоящее время этот подход очень популярен, поскольку в его рамках могут быть описаны многие классические задачи. Он лежит в основе всех проектов, предполагающих эвристический поиск, и наиболее современного его варианта - недетерминированного алгоритма [1, 2, 6] в качестве метода представления модели. Все они предполагают ре-шеткоподобную систему памяти и, таким образом, неразрывно связаны с методом приписывания при представлении изменений в среде. Но, как уже говорилось выше, этот метод становится неадекватным для более сложных областей. Пусть, например, чашка стоит на блюдце. Если мы передвинем блюдце, чашка передвинется вместе с ним, но если мы переместим чашку, блюдце, очевидно, останется на прежнем месте. Нетрудно привести и более сложные примеры такого рода. [27]

Страницы: 1 2