Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Например, можно создать машину Тьюринга, которая не только распознает любое предложение ж из языка DIV3, но и выводит на ленту число ж/3. Назовем эту машину Div3-Comp. Для простоты предположим, что исходная строка записана в троичном виде. Тогда исходная строка принадлежит языку DIV3, если и только если ее последняя цифра равна нулю, а результатом деления ж/3 является содержимое ленты, полученное после стирания последней цифры, равной нулю, если эта цифра не является единственным символом на ленте. Если предположить, что машина Div3-Comp должна вводить и выводить только двоичные числа, то ее реализация может выглядеть следующим образом. Сначала переведем исходную строку ж из двоичного вида в троичный, получим результат деления ж/3, а затем переведем ответ в двоичный вид. Очевидно, что эти преобразования можно автоматически выполнить цифра за цифрой за с|ж| тактов, где с — константа.
Глава 4. Вычислительная сложность
125
Следовательно,
TDiv3-Comp(N) ^ с\х1
где С — константа. Очевидно, что класс V должен содержать задачу, которую можно решить с помощью машины Div3-Comp.
В пользу того, что класс V содержит полиномиальные вычислительные задачи, говорят следующие рассуждения общего характера. Вычислительное устройство, имеющее неймановскую архитектуру (иначе говоря, всем известную современную компьютерную архитектуру [227]), состоит из счетчика, памяти и центрального процессора (central processor unit — CPU), поочередно выполняющего элементарные команды, называемые микрокомандами.
Load (Загрузить) Загрузить содержимое из памяти в регистр цен-
JumpZ (Условный переход) Выполнить команду Jump, если содержимое регистра равно нулю.
Хорошо известно (см. раздел 1.4 в работе [9]), что перечисленных выше микрокоманд достаточно для создания алгоритмов, решающих любые арифметические задачи на неймановском компьютере. (Однако следует заметить, что выражение "любые арифметические задачи" не означает "предложения произвольного размера".) Можно доказать (см. теорему 1.3 в работе [9]), что каждую микрокоманду из указанного выше набора, можно имитировать на машине Тьюринга за полиномиальное время. Следовательно, задачу, которую можно решить за полиномиальное время на неймановском компьютере (т.е. количество микроинструкций, используемых в алгоритме, представляет собой значение полинома, зависящего от размера исходных данных), можно решить за полиномиальное время и с помощью машины Тьюринга. Это возможно благодаря тому, что для любых полиномов р(п) и q{n) произвольные арифметические комбинации p(n), q(n), p(g(n)) и q(p(ri)) также являются полиномами, зависящими от аргумента п. Отметим, что из множества микрокоманд произвольно исключены операции умножения и деления. Умножение двух чисел размера п выполняется с помощью п сложений. Следовательно, затраты, связанные с операцией умножения, вычисляются по формуле п х 3arpaTbi(Add). Затраты на деление равны затратам на умножение, поскольку
Store (Сохранить) Add (Сложить) Сотр (Дополнение)
Jump (Перейти)
трального процессора.
Сохранить в памяти содержимое регистра.
Сложить содержимое двух регистров.
Вычислить дополнение к содержимому регистра
(для вычитания с помощью операции Add).
Присвоить счетчику новое значение.
Stop (Остановиться)
Прекратить работу.
126
Часть II. Математические основы
деление можно свести к повторному выполнению операции вычитания, которая представляет собой сложение дополнений.
Следует упомянуть о некоторых несущественных различиях между неймановским компьютером и машиной Тьюринга. По определению 4.1 задача считается разрешимой с помощью машины Тьюринга тогда и только тогда, когда любой вариант задачи можно решить с помощью одной и той же машины ("одна машина решает все варианты задачи"). Затраты, связанные с решением задачи с помощью машины Тьюринга, равномерно зависят от размера задачи. Предварительные ограничения на размеры задачи необязательны. Машина Div3 в примере 4.1 наглядно иллюстрирует это утверждение. Благодаря этому свойству оценки затрат, используемые для измерения сложности вычислений на машине Тьюринга, являются равномерными (uniform cost measure). В противоположность этому регистровые и логические схемы, представляющие собой базовые строительные блоки неймановского компьютера, имеют фиксированный размер. Следовательно, задачи, разрешимые с помощью неймановского компьютера, должны иметь заранее фиксированный размер: чем больше вариант одной и той же задачи, тем больший компьютер требуется для ее решения. В общем, машины разных размеров не соответствуют равномерным оценкам затрат, связанных с ее решением. Следовательно, оценки затрат в неймановской модели вычислений носят неравномерный характер. Однако до сих пор разница между оценками равномерных и неравномерных затрат не создала ни одного нового класса сложности и не разрушила ни одного существующего класса. По этой причине мы утверждаем, что эта разница несущественна.
В оставшейся части главы мы будем часто пренебрегать различиями между задачами принятия решений и вычислительными задачами, а также между вычислениями с помошью машины Тьюринга, современного компьютера, процедуры или алгоритма. Задачи принятия решений и вычислительные задачи будут называться просто задачами, а машины, компьютеры, процедуры и алгоритмы будут называться просто методами или алгоритмами. Иногда мы будем упоминать задачу распознавания языка и только в этом случае будем использовать машину Тьюринга в качестве основного инструмента вычислений.
