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


[Старт] [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]


128

Puc, 12,4, Вычисление no программе M при входе 10100

Функция перехода 5 определена таблицей, где величина, записанная в Г строке и S столбце, есть значение 5 (q, S). Рис. 12.4 иллюстрирует по программе Мпри входе х= 10100, здесь указаны состояние, распространение головки и содержание пустых ячеек ленты до и после каждого шага.

Заметим, что вычисление после восьми шагов оканчивается в состоянии Яу, поэтому на входе 10100 ответом будет «да». В общем случае будем говорить, что программа М, имеющая входной алфавит Г, принимает X е 27* в том и только в том случае, когда, будучи примененной ко входу X, она останавливается в состоянии qy . Язык Lm, распознаваемый программой М, задается следующим образом: Lm= {X е F: М принимает JO-

Нетрудно видеть, что программа, представленная на рис. 12.3, распознает язык: {X е {0,1}; два последних символа словаXявляются нулями}.

Отметим, что это определение распознавания языка не требует, чтобы программа М останавливалась при всех входах из 2?". М обязана останавливаться лишь при входах L.

Если X е I* \ Lm, то работа программы М на X может либо заканчиваться в состоянии Qn, либо может бесконечно продолжаться без остановки. Однако ДМТ-программа, соответствующая нашему пониманию



алгоритма, должна останавливаться на всех словах входного алгоритма. В этом смысле программа на рис. 12.3. является алгоритмической, так как, начиная работать на любом слове из символов 0,1, она будет останавливаться.

Соответствие между «распознаванием» языков и «решением» задач распознавания определяется следующим образом. Будем говорить, что ДМТ-программа М решает задачу распознавания II при кодировании е, если М останавливается на всех словах, составленных из букв входного алфавита 1 = L [II, е]. Программа на рис. 12.3 иллюстрирует это соответствие.

Пример. Делимость на четыре. Дано положительное число N. Существует ли положительное число m такое, что Л= 4т.

При стандартном кодировании целое число N представляется словом из 0,1, т.е. двоичной записью этого числа. Так как положительное целое число делится на четыре тогда и только тогда, когда последние две цифры двоичной записи этого числа являются нулями, то программа, изображенная на рис. 12.4, «решает» при нашем стандартном кодировании задачу «делимость на четыре».

Заметим, что ДМТ-программой можно пользоваться и для вычисления функций. Предположим, что программа М, имеющая входной алфавит Е и ленточный алфавит Г, останавливается на любом входе из I*. Тогда М вычисляет функцию /м.Г* которая для каждого X е 2

определяется следующим образом. Если программа М, начиная работать при входе X, останавливается, то в качестве /м (Х) берется слово, составленное из символов, записанных после остановки машины в ячейке с номерами 1, 2, 3, включая последнюю пустую ячейку. Программа М, представленная на рис. 12.4, вычисляет функциюУл:{0, 1}* -> {О, 1, Ь}*, которая отображает каждое словоX е {0,1 }* в слово fM, получаемое из X удалением двух крайних справа символов (если \Х\<2, то М вьщает в качестве пустое слово). Хорошо известно, что ДМТ-программы могут решать задачи намного более сложные, чем в рассмотренном примере. Несмотря на то что ДМТ имеет только одну последовательную ленту и на каждом шаге может выполнять весьма ограниченную работу, ДМТ-программа может быть составлена так, что проведет любое вычисление, выполняемое обычным компьютером.

Далее определим понятие «временная сложность». Время, требуемое ДМТ-программой Мдля вычисления при входе X, есть число шагов, выполняемых до момента остановки. Если программа Л/останавливается на



всех входах X G 27*, то временную сложность Т: 2 -> 2 можно определить так:

Tm(N) =max

существует такое слово Х&\х\=п т: что вычисление по программе М на входе X требует времени т J

Детерминированная программа М называется полиномиальной ДМТ-программой, если существует такой полином Р, что для всех п е 2, Гд {п)<Р{п).

Далее определим формально первый важный класс языков - класс Р. Он определяется следующим образом: Р = {L: существует полиномиальная ДМТ-программа М, для которой L = L}.

Будем говорить, что задача распознавания II принадлежит классу Р при кодировании е, если i(II, е) е Р, т.е. существует полиномиальная программа ДМТ-программа, которая «решает» задачу при кодировании е. Далее мы не будем приводить конкретные схемы кодирования, а будем говорить, что задача распознавания II принадлежит классу Р.

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

В настоящем разделе вводится второй важный класс языков (задач распознавания свойств) - класс NP. Прежде чем перейти к формальному определению этого класса в терминах язьпсов и машин Тьюринга, поясним смысл понятия, лежащего в основе определения класса NP.

Рассмотрим задачу коммивояжера. В условии даны множества городов, расстояние между ними и граница В. При этом спрашивается, существует ли маршрут, проходящий через все города, и длины, не превосходящий В, Полиномиальный алгоритм этой задачи неизвестен. Предположим, однако, что относительно некоторой индивидуальной задачи кто-то получил ответ «да». Если вы в этом сомневаетесь, то можно потребовать доказательство этого факта, заключающегося в предъявлении маршрута, обладающего необходимыми свойствами. Имея предъявленное решение, нетрудно проверить является ли оно на самом деле маршрутом и если это так, вычислить его длину, сравнить ее с границей В и тем самым проверить соответствующее утверждение. Более того, эту «процедуру проверки» можно представить в виде алгоритма, временная сложность которого ограничена полиномом от Length (/). Именно понятие полиномиальной проверяемости позволяет вьщелить задачи класса NP. Отметим, что проверяемость за полиномиальное время не влечет

[Старт] [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]