Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Поскольку случайные такты, выполняемые в ходе п запусков машины РМ(1), являются независимыми, каждый запуск машины РМ{1) может считаться испытанием Бернулли, у которого вероятность успеха равна е(<5 — для стойкости), а вероятность неудачи — 1 — е(1 — 5 — для непротиворечивости). Применяя биномиальное распределение (раздел 3.5.2), приходим к выводу, что при "голосовании
Величина <5 представляет собой вероятность ошибки второго рода. — Прим. ред.
140
Часть II. Математические основы
большинством" вероятность ошибки для машины РМ'(1, п) равна вероятности того, что в п испытаниях Бернулли количество успехов равно или больше [||J +1. Для полноты эта сумма равна
71
e(n) = Prob[c?l^ [fj+l] = ]? b(i;n,e). (4.4.5)
i=[f+ij+i
Для непротиворечивости оценка имеет следующий вид:
71
ё (n) = Prob [Vn >[^\+т]= Е Ь&п'(4А6>
j=[f+ij+i
Эти два выражения представляют собой суммы соответствующих биномиальных вероятностей. Поскольку е > \ и ё < |, центральный член (см. раздел 3.5.2.1) первого распределения расположен в точке (п + 1) е > J +1. (В этой точке биномиальный член достигает максимума.) Центральный член второго распределения находится в точке (п + 1) ё > [^J + 1.
Поведение этих сумм было рассмотрено в разделе 3.5.2.1. Сумма в выражении (4.4.6) представляет собой правый хвост биномиального распределения, поскольку [t|J + 1 > (п + 1) ё. Применяя формулу (3.5.7) и полагая г = [^j^J и р = ё, получаем, что
., . 2(1 -6) 1
^n)<(i=W^i-
Поскольку число ё — константа,
6(п) —> 0 при п —> со. Читатели могут самостоятельно получить аналогичный результат для полноты:
е(п) > 1 - -, п
где с — некая константа (упражнение 4.7).
Поскольку хвосты стремятся к нулю быстрее5, чем ^, положив п = |/|, приходим к выводу, что машина РМ'(1,п) работает \1\ ¦ poly(\I\) единиц времени, где poly(\I\) — время работы машины РМ, на вход которой поступает предложение /. Следовательно, машина РМ' по-прежнему имеет полиномиальное время выполнения.
5Оценки (3.5.7) и (3.5.8) являются лишь оценками сверху. Реальная скорость убывания хвостов к нулю намного превышает —. Числовые иллюстрации приведены в примере 3.9. Это свойство будет в дальнейшем подтверждено изучением полноты и непротиворечивости протокола 18.4 в разделе 18.5.1.1.
Глава 4. Вычислительная сложность
141
4.4.1.2 Почему оценки не равны |?
Если бы выполнялось условие е — 5 = ^, то центральный член обоих распределений (4.4.5) и (4.4.6) находился бы в точке J. Легко проверить, что при нечетном числе п
е (п) = 5 (п)
а при четном
е (п) =з 5 (п)
Иначе говоря, величина е(п) никогда не увеличивается, а величина <5(п) — никогда не уменьшается — независимо от количества запусков машины РМ(1), они равны (или почти равны) ^. Итак, машина РМ'{1), представляющая собой п независимых запусков машины РМ(1), не может прийти ни к какому решению, поскольку и полнота, и непротиворечивость этой машины равны ^, т.е. в половине случаев машина распознает предложение, а половине случаев — нет. Если количество запусков не ограничено и машина РМ{1) не принимает никаких решений, машина РМ'{1) никогда не завершит работу и, следовательно, не может быть полиномиальным алгоритмом.
Итак, поскольку класс VP представляет собой класс языков, предложения которых распознаются за полиномиальное время с определенной вероятностью, необходимо потребовать, чтобы величины ей 5 отличались от ^.
Однако следует отметить, что это требование является необходимым лишь для наиболее общих вариантов задач распознавания языков, принадлежащих классу W, который содержит подкласс задач с "ошибками, имеющими двусторонние оценки" (раздел 4.4.5). Если ошибка ограничена только с одной стороны (например, е = 1 или 5 = 0, как в разделах 4.3 и 4.4.4), условие е/^и<5/|не обязательно, поскольку в односторонних алгоритмах не используется критерий "голосования большинством". Вместо него можно применить критерий "голосования меньшинством" ("minority election criterion"). Например, можно использовать критерий "единогласного голосования" ("unanimous election criterion"), в котором машина РМ'(1) распознает (отклоняет) предложение /, только если все п запусков машины РМ{1) завершились одинаково. В таких случаях е{п) —> 1 или 5{п) —» 0 при п —> со с экспоненциальной скоростью при любых е, 5 € (0,1).
На практике возможны ситуации, когда е ^ ^ или 5 ^ ^ (однако, как мы уже указывали, эти неравенства не обязаны выполняться одновременно). Для таких задач изменение критерия голосования (например, на голосование меньшинством) может намного увеличить или уменьшить ошибку распознавания. В разделе 18.5.1 мы рассмотрим протокол, имеющий вероятность распознавания, равную е = ^, и увеличим вероятность полноты, повторив его с применением критерия "голосования меньшинством".
142
Часть II. Математические основы
Подклассы класса VP
Класс W содержит несколько подклассов, характеризующихся разной степенью полноты и непротиворечивости. Рассмотрим их поближе. Каждый из этих классов можно упростить с помощью некоего алгоритма. Аналогично детерминированной машине Тьюринга, моделирующей полиномиальный алгоритм, вероятностная машина Тьюринга имитирует рандомизированный полиномиальный алгоритм (randomized polynomial-time algorithm). Следовательно, примеры алгоритмов, рассмотренные во введении, не ограничены распознаванием языков.
