назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [ 129 ] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


129

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

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

1)стадии угадывания;

2)стадии проверки.

По заданной индивидуальной задаче / на первой стадии происходит просто «угадывание» некоторой структуры 5. Затем задача 1и S вместе подаются в качестве входа на стадию проверки, которая вьшолняется обычным детерминированным способом и заканчивается либо ответом «да», либо ответом «нет», либо продолжается бесконечно без остановки. Недетерминированный алгоритм «решает» задачу распознавания II, если для любой индивидуальной задачи I е Du выполнены следующие условия:

1)если / е Гц, то существует такая структура 5, угадывание которой для входа / приведет к тому, что стадия проверки начинает работу на входе (/, S), заканчивается ответом «да»;

2)если / е Гц, то не существует такой структуры 5, угадывание которой для входа / обеспечило бы окончание стадии проверки на входе (/, S) ответом «да».

Например, недетерминированный алгоритм решения задачи коммивояжер можно было бы построить, используя в качестве стадии угадывания просто выбор произвольной последовательности городов, а в качестве стадии проверки упомянутую, полиномиальную процедуру и проверку доказательства для задачи коммивояжер. Очевидно, для любой индивидуальной задачи / найдется такая догадка S, что результатом работы стадии проверки на входе (/, S) будет «да» в том и только в том случае, если для индивидуальной задачи / существует маршрут искомой длины.

Говорят, что недетерминированный алгоритм, решающий задачу распознавания II, работает в течение полиномиального времени, если найдется полином Р такой, что для любого / е Гц найдется такая догадка 5, приводящая на стадии детерминированной проверки на входе (/, S) к от-



вету «да» за время P(Length [i]). Отсюда следует, что «размер» угадываемой структуры S будет обязательно ограничен полиномом от Length [/], так как на проверку догадки S может быть затрачено не более чем полиномиальное время.

Класс NP, определяемый неформально, это класс всех задач распознавания II, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за полиномиальное время. Приведенный пример показывает, что задача коммивояжер принадлежит NP.

Поясним значение термина «решает» в этом определении. Основное назначение «полиномиального недетерминированного алгоритма» состоит в объяснении понятия «проверяемости за полиномиальное время», а не в том, чтобы служить реалистическим методом решения задач распознавания свойств.

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

Имеется еще одно важное отличие «решения» задачи распознавания недетерминированным алгоритмом от решения детерминированным алгоритмом, а именно в первом случае отсутствует симметрия между ответами «да» или «нет». Если задача «дано /; верно ли что для I выполняется свойство X» может быть решена полиномиальным (детерминированным) алгоритмом, то такое же утверждение справедливо и для дополнительной задачи: «Дано /, верно ли, что для / не выполняется свойство Х7». Детерминированный алгоритм останавливается при всех входах, поэтому достаточно поменять местами ответы «да» и «нет» (переставить состояния дуидв ДМТ-программе).

Неочевиден этот факт для всех задач, разрешаемых за полиномиальное время недетерминированными алгоритмами. Рассмотрим, например, дополнение задачи коммивояжер: дано множество городов, расстояние между ними и граница 5. Верно ли, что нет маршрута, проходящего через все города и имеющего длину, не превосходящую В? Для выяснения, имеет ли поставленный вопрос ответ «да», неизвестен способ, который был бы короче, чем проверка всех (или почти всех) возможных маршрутов. Иными словами неизвестен полиномиальный недетерминированный алгоритм решения этой дополнительной задачи из NP.

В заключение формализуем приведенное определение в терминах языков и машин Тьюринга. Формальным эквивалентом недетерминированного алгоритма является программа для недетерминированной одно-ленточной машины Тьюринга (НДМТ).



Модель НДМТ, которой мы будем пользоваться, имеет в точности такую же структуру, как ДМТ (рис. 12.5). Отличие состоит в том, что НДМТ дополнена угадывающим модулем со своей головкой, которая может только записывать на ленту. Угадывающий модуль дает информацию для записывания «догадки» и применяется исключительно с этой целью.

Угадьшающий модуль

угадывающая головка

Управляющее устройство

читающая (пишущая) головка

-3 -2 -1

Рис. 12.5

Программа НДМТ или НДМТ-программа определяется точно так же, как ДМТ-программа, при этом используется ленточный алфавит Г, входной алфавит I, пустой символ Ь, множество состояний начальное состояние qo, заключительные состояния qy и q, функция перехода 5(Q\ { }) X Г- 2 X Г X {-1, +1}. Вычисление НДМТ-программы при входе X g 27* в отличие от вычислений ДМТ-программы имеет две различные стадии. На первой стадии происходит «угадывание». В начальный момент времени входное слово X записывается в ячейке с номерами 1, 2, 3, \Х\ (остальные ячейки пусты), читающая / пишущая головка «смотрит» на ячейку с номером 1, пишущая головка угадывающего модуля «смотрит» на ячейку с номером -1, а устройство управления «пассивно». Затем угадывающий модуль начинает управлять угадывающей головкой, которая делает один шаг в каждый момент времени и либо пишет в находящейся под ней ячейке одну букву из алфавита Г и сдвигается на одну ячейку влево, либо останавливается. В последнем случае угадывающий модуль переходит в пассивное состояние, а управляющее устройство начинает работу в состоянии до. Угадывающий модуль решает, продолжить ли работу (перейти ли в пассивное состояние, какую букву из Г написать на ленте), причем делается это совершенно произвольно. Таким образом, угадывающий модуль до момента окончания своей работы может написать любое слово из Г* и в действительности может никогда не остановиться.

Стадия проверки начинается в тот момент, когда управляющее устройство переходит в состояние до . Начиная с этого момента, вычисле-396

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [ 129 ] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]