Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Вероятность того, что недетерминированная машина Тьюринга сделает ошибку, решая задачу принятия решений, ограничена константой (вероятностным пространством является случайная лента машины).
Недетерминированную машину Тьюринга с ограниченной ошибкой мы будем называть вероятностной машиной Тьюринга (probabilistic Turing machine). По этой причине название "недетерминированная машина Тьюринга" на самом
2Точный смысл выражения "эффективная машина" будет определен в разделе 4.4.6. Пока буцем считать, что эффективность означает быстродействие.
138
Часть II. Математические основы
деле означает другой класс задач принятия решений, который будет рассмотрен в разделе 4.5.
Вероятностная машина Тьюринга имеет несколько лент. Одна из этих лент называется случайной (random tape) и содержит равномерно распределенные случайные символы. Сканируя исходное предложение /, машина взаимодействует со случайной лентой, считывает случайный символ, а затем работает как детерминированная машина Тьюринга. Случайная строка называется случайным вводом (random input) вероятностной машины Тьюринга. Из-за наличия случайного ввода распознавание исходного предложения / вероятностной машиной Тьюринга уже не является детерминированной функцией, а зависит от случайной величины. Иначе говоря, распознавание представляет собой функцию, зависящую от случайного машинного ввода. Эта случайная переменная определяет некую вероятность ошибки (error probability) при распознавании предложения I.
Класс языков, которые распознаются вероятностными машинами Тьюринга, называется классом вероятностных полиномиальных языков (PPT languages — probabilistic polynomial-time languages), и обозначается символами PP.
Определение 4.5 (Класс РР). Символами РР обозначается класс, обладающий следующими свойствами. Говорят, что язык L принадлежит классу РР, если существует вероятностная машина Тьюринга РМ и полином р(п), такие что машина РМ распознает любое предложение IsLc определенной вероятностью ошибки, представляющей собой случайную переменную, зависящую от случайного такта машины РМ, за время Трм(п) ^ р(п) для всех неотрицательных целых чисел п, где п — длина предложения I.
В определении 4.5 остался один неясный момент: "машина РМ распознает любое предложение / € L с определенной вероятностью ошибки". Выражение "определенная вероятность ошибки" должно быть уточнено с помощью двух выражений, содержащих оценки условной вероятности.
Вероятностным пространством является случайная лента машины РМ.
Выражение (4.4.1) представляет собой оценку вероятности правильного распознавания предложения. Она называется оценкой полноты (completeness probability bound).3 Термин "полнота" означает, что любое предложение языка в конце
'Величину иногда называют чувствительностью алгоритма распознавания. Соответственно, величина 1-е представляет собой вероятность ошибки первого рода. — Прим. ред.
Prob[PM распознает J € L\I е L] ^ е, Prob[PM распознает J Е L\I g L] ^ <5,
где числа еий - константы, удовлетворяющие условиям
(4.4.1) (4.4.2)
(4.4.3)
Глава 4. Вычислительная сложность
139
концов оказывается распознанным. Оценка этой вероятности снизу необходима для того, чтобы ограничить возможность ошибочно отклонить предложение. Более точное представление выражения (4.4.1) выглядит следующим образом.
РгоЬ[РМ приходит к выводу, что / $ L\I е L] < 1 — е. (4.4.4)
Число 1-е является вероятностью ошибочного отклонения предложения /. В таких случаях говорят, что полнота машины РМ ограничена вероятностью ошибочно отклонить предложение I.
Выражение (4.4.2) представляет собой вероятность ошибочного распознавания предложения, не принадлежащего языку. Это выражение называется оценкой непротиворечивости (soundness probability). Термин "непротиворечивость" означает, что предложение, не принадлежащее языку, никогда не распознается. Необходимость ограничить вероятность такой ошибки очевидна. В таких случаях говорят, что непротиворечивость машины РМ ограничена вероятностью ложного распознавания.4
4.4.1 Вероятность ошибки
Вероятность ошибки для машины РМ ограничена двумя константами, е и 5, принадлежащими интервалам, указанным в выражении (4.4.3). Покажем, что, хотя точное значение данных констант не определено, это не создает никаких проблем.
4.4.1.1 Характеристики полиномиального времени
Если п раз применить к исходному предложению / вероятностную машину Тьюринга РМ, полнота которой ограничена величиной ее 1], а непротиворечивость — числом 5 € [0, то это повторение, обозначенное как РМ'{1,п), также окажется вероятностной машиной Тьюринга. В качестве критерия для распознавания или отклонения предложения I машиной РМ'(1, п) можно использовать "голосование большинством" ("majority election criterion"). Иначе говоря, если [t|J +1 раз запуск машины РМ(1) завершался распознаванием (отклонением), то машина РМ'(1, п) распознает (отклоняет) предложение /. Очевидно, что полнота и непротиворечивость машины РМ'(1, п) зависит от числа п. Покажем, что алгоритм РМ'(1,п) по-прежнему имеет полиномиальное время выполнения, зависящее от размера предложения /.
