Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Следует отметить, что в определении 4.1 нечеткие ограничения "любое предложение I G L" и "для всех неотрицательных целых чисел п" имеют большое значение. В работах, посвященных теории вычислительной сложности, задача считается решенной, только если любой экземпляр данной задачи можно решить с помощью одной и той же машины Тьюринга (т.е. с помощью одного и того же метода). Только в этом случае алгоритм считается достаточно общим и может называться методом. Для иллюстрации рассмотрим следующий пример.
Пример 4.1 (Язык DIV3). Пусть DIV3 — множество неотрицательных целых чисел, кратных трем. Покажем, что DIV3 G V.
Для того чтобы распознать язык DIV3 за полиномиальное время, построим машину Тьюринга с одной лентой.
Сначала заметим, что если записать исходные данные в виде троичных чисел (в позиционной системе счисления по основанию 3), т.е. в виде строки символов из множества {0,1,2}, то задача распознавания становится тривиальной: исходная строка х принадлежит языку DIV3 тогда и только тогда, когда последняя цифра в строке х равна нулю. Следовательно, создаваемая машина должна просто перемещать головку вправо, пока не обнаружит пустой символ. Машина должна остановиться и выдать ответ "ДА", если и только если последний непустой символ был равен нулю. Очевидно, что данная машина может распознавать любое предложение, состоящее из цифр, причем количество шагов алгоритма равно длине исходной строки. Следовательно, DIV3 G V.
Однако требуется еще доказать, что факт DIV3 е V не зависит от способа представления исходной строки (т.е. основания позиционной системы счисления). Для этого достаточно рассмотреть случай, когда исходная строка представлена в двоичном виде. Назовем создаваемую машину Div3. Конечное управляющее устройство машины Div3 выполняет следующий такт, руководствуясь функцией, описанной на рис. 4.2.
Покажем, что машина Div3, определенная функцией, представленной на рис. 4.2, является достаточно общей для распознавания всех предложений в языке DIV3.
Глава 4. Вычислительная сложность
123
Текущее Символ Следующий Новое
состояние на ленте такт состояние
9о 0 вправо яо
(начальное 1 вправо ч\
состояние) пустой "Звонок" & Стоп
0 вправо яг
1 вправо яо
яг 0 вправо ч\
1 вправо чг
Рис. 4.2. Операции машины Div3
Во-первых, для распознавания того факта, что двоичная строка х принадлежит языку DIV3, машине Div3 достаточно трех состояний, соответствующих ситуациям, когда ее головка сканирует строки ЗА;, ЗА; + 1 и ЗА; + 2 (для А; ^ 0) соответственно. Наименьшая исходная строка равна нулю. Следовательно, после сканирования нулевой строки машина Div3 должна остаться в начальном состоянии. Без ограничения общности будем обозначать начальное состояние через qo, состояние, в которое переходит машина Div3, сканируя исходную строку, состоящую из единицы, — через gi, а состояние, в которое переходит машина Div3, сканируя исходную строку, состоящую из двойки (= (10)2)', — через q2.
Приписав справа к неотрицательному двоичному целому числу а нуль (или единицу), мы получим число 2а (или 2а+1 соответственно). Следовательно, после сканирования числа а = Зк машина Div3 должна остаться в начальном состоянии, если следующий сканируемый символ является нулем, поскольку в этом случае 2а = 6к = ЗА;'. Если следующий сканируемый символ равен единице, машина должна перейти в состояние qi, поскольку 2а+1 = 6А; + 1 = ЗА;' +1. Аналогично после сканирования числа а = Зк+1 машина Div3 из состояния q\ должна перейти в состояние q2, если 2а = 6А; + 2 = ЗА;' + 2, или в состояние до. если 2а+1 = 6к + + 3 = ЗА;'. Остальные два варианта относятся к ситуации, когда а = Зк + 2: если 2а = 6А; + 4 = ЗА;' + 1 машина Div3 переходит из состояния q2 в состояние q\, а если 2а + 1 = 6А; + 5 = ЗА;' + 2, машина Div3 остается в состоянии q2.
'Мы используем символы (ai<X2 ... ап)ь при ai < Ь и г = 1,2,..., п для обозначения числа, записанного в позиционной системе счисления по основанию Ь. Когда Ь = 10 и 6 = 2, основание системы счисления часто не указывается, если это не вызывает недоразумений.
124
Часть II. Математические основы
Итак, машина Div3 завершает сканирование строк ЗА;, ЗА; + 1 и ЗА; + 2 (для А; ^ 0), пребывая в состоянии qo, q\ или q% соответственно. Теперь, если головка обнаружит пустой символ, машина остановится и выдаст ответ "ДА", только если она пребывает в состоянии qo. В остальных ситуациях машина Div3 прекращает работу, не завершив распознавания.
Легко показать, что Т^цп^ = п. Следовательно, машина Div3 распознает язык DIV3 за полиномиальное время. ?
Пример 4.2.
1. Битовая строка 10101(= (21)ю) распознается. Машина Div3 распознает ее за rDiV3(|ioioi|) = 1101011 = 5 тактов.
2. Битовая строка 11100001(= (225)ю) распознается. Машина Div3 распознает ее за TDiv3(|1110000i|) = |11100001| = 8 тактов.
3. Битовая строка 10(= (2)ю) не распознается. Машина Div3 находит ответ за два такта. ?
4.3.1 Полиномиальные вычислительные задачи
По определению класс V является классом языков, распознаваемых за полиномиальное время. Задача распознавания языка является задачей принятия решений (decisional problem). При любых исходных данных результатом решения такой задачи является ответ "ДА" или "НЕТ". Однако класс V является более широким и содержит полиномиальные вычислительные задачи (polynomial-time computational problems). При любых исходных данных результатом решения таких задач является более общий ответ, чем "ДА" и "НЕТ". Поскольку машина Тьюринга может записывать символы на ленту, она позволяет решать такие задачи.
