Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Алгоритм 4.8. Square-Free(7V,^)(A^))
Читатели, знакомые с функцией Эйлера, могут убедиться в правильности алгоритма 4.8 (упражнение 4.13). Верификация алгоритма достигается благодаря факту из теории чисел, который будет описан в главе 6 (раздел 6.3). Анализ временной сложности алгоритма поиска наибольшего общего делителя (раздел 4.3.2.3) показывает, что она полиномиально зависит от размера числа N.
'ДА", если не существует простого числа р, такого что р
«2 | 7V.
единиц времени, т.е. временная сложность экспоненци-
1. d«-gai(Ar,<KJV));
2. if d = 1 или d2 J N ответ "ДА" else ответ "НЕТ".
Глава 4. Вычислительная сложность
159
Рис. 4.4. Все возможные такты недетерминированной машины Тьюринга при решении задачи распознавания
Опишем некое вычислительное устройство, моделирующее метод решения задач, принадлежащих тому же классу сложности, что и задача SQUARE-FREENESS Ход вычислений описывается на рис. 4.4.
Это устройство называется недетерминированной машиной Тьюринга (non-deterministic Turing machine). На каждом такте этой машины существует конечное количество вариантов следующего такта. Входная строка считается распознанной, если существует хотя бы одна последовательность разрешенных тактов, начинающаяся считыванием первого символа строки и завершающаяся считыванием последнего символа. Такая последовательность тактов называется последовательностью распознавания (recognition sequence).
Работу недетерминированной машины Тьюринга можно представить в виде серии догадок. В этом случае последовательность распознавания представляет собой серию правильных догадок. Таким образом, все возможные такты образуют дерево, называемое вычислительным деревом (computational tree) недетерминированной машины Тьюринга. Совершенно очевидно, что размер (количество узлов) этого дерева экспоненциально зависит от размера входа. Однако, поскольку количество тактов в последовательности распознавания входной строки равно глубине дерева d, получаем, что d = 0(к^(количество узлов дерева)) и количество тактов в последовательности распознавания полиномиально зависит от размера
160
Часть II. Математические основы
входной строки. Итак, временная сложность распознавания строки с помощью серии правильных догадок полиномиально зависит от размера исходных данных.
Определение 4.8 (Класс ЛЛР). Язык принадлежит классу NV, если он распознается недетерминированной машиной Тьюринга за полиномиальное время.
Очевидно, что
VQNV.
Точнее говоря, каждый язык (задача принятия решений), принадлежащий классу V, тривиально распознается недетерминированной машиной Тьюринга. Точно так же легко убедиться, что
ZVV, ^(Монте-Карло),7>Р (Лас-Вегас) С NV.
Действительно, классы ZVV, ^^(Монте-Карло) и ^^(Лас-Вегас), по существу, являются подклассами класса NV, поскольку содержат задачи, для решения которых требуются недетерминированные полиномиальные алгоритмы6. Единственная причина, по которой задачи, принадлежащие этим подклассам, допускают эффективное решение, заключается в том, то эти NP-задачи содержат много дополнительной информации, позволяющей делать правильные догадки. По общепринятому соглашению класс NV считается классом недетерминированных полиномиальных задач принятия решений, имеющих немногочисленные свидетельства (sparse witnesses). Смысл выражения "немногочисленные свидетельства" заключается в следующем: для вычислительного дерева решения NP-задачи дробь
количество последовательностей распознавания количество всех последовательностей
является пренебрежимо малой (определение 4.13). В разделе 18.2.3 будет показано, что
ЛГГСРГ. (4.5.1)
Если NP-задача обладает немногочисленными свидетельствами, то недетерминированная машина Тьюринга, использующая случайные догадки, не гарантирует эффективного алгоритма для ее решения. Этим NP-задачи с немногочисленными свидетельствами отличаются от NP-задач с большим количество свидетельств. Для NP-задач с фрагментарными свидетельствами недетерминированные машины Тьюринга просто моделируют класс задач принятия решений, обладающих следующими свойствами.
'Вспомните причину, по которой в начале раздела 4.4 мы назвали подкласс недетерминированных полиномиальных машин Тьюринга "вероятностными машинами Тьюринга".
Глава 4. Вычислительная сложность
161
При наличии свидетельств ответ на задачу принятия решения можно получить за полиномиальное время.
Свидетельство для NP-задачи моделируется последовательностью распознавания в вычислительном дереве недетерминированной машины Тьюринга (пунктирные линии на рис. 4.4).
Возникает вопрос: какова временная сложность решения произвольной NP-задачи без наличия свидетельств? Ответ неизвестен. Все существующие алгоритмы решения произвольных NP-задач без использования свидетельств имеют полиномиально неограниченную временную сложность. Еще никому не удалось доказать, что V Ф MV. Кроме того, противоположный факт, т.е. V = MV, также не доказан. Вопрос
V = MV1
является хорошо известной нерешенной задачей в области теории компьютерных наук.
Определение 4.9 (Нижние и верхние оценки сложности). Величина В называется нижней оценкой сложности задачи Р, если любой алгоритм А решения задачи Р имеет сложность С(А) ^ В. Величина U называется верхней оценкой сложности задачи Р, если любой алгоритм А решения задачи Р имеет сложность С(А) ^ U.
