Классы языков, основанные на рандомизации

Вероятностная машина отличается от детерминированной тем, что в левой части инструкции появляется еще один символ - выходное значение датчика случайных чисел с конечным алфавитом, который на каждом шаге работы выдает свои значения равновероятно и независимо от значений, выданных на других шагах. Вероятность “p” вычисления на вероятностной машине на входе “x” результата “y” равна сумме вероятностей всех реализаций “y” на входе “x”. Говорят, что машина выдает результат “y” для входа “x” со сложностью m (временной, ленточной) и вероятностью “p”, если на входе “x” с вероятностью не меньшей p, израсходовав не более m единиц (шагов, ячеек памяти), машина останавливается с результатом “y”. Таким образом, для вероятностной машины возможно, хотя и с малой долей вероятности, получить неверный результат.

Быстродействие вероятностных машин по сравнению с детерминированными объясняется тем, что для вероятностной машины возможны различные реализации ее работы на одном и том же аргументе, и вероятность того, что среди этих реализаций найдутся сравнительно короткие может быть достаточно высокой.

Две теоремы Фрейвальда1) показывают, что переход к вероятностным вычислениям приводит к выигрышу не только во времени, но и в пространстве (емкости).

Здесь будут рассмотрены два класса языков, определяемых машинами Тьюринга, использующими при вычислениях случайные числа. Примером радомизированного алгоритма может служить алгоритм “быстрой сортировки”: из списка a₁, a₂,…,a _n выбирается ведущий элемент a _v, после чего список распадается на два – соответственно, меньших и больших a _vэлементов. Далее можно рекурсивно отсортировать оба списка, в результате получится отсортированный список a₁, a₂,…,a _n. Выбор ведущего элемента в списке случаен с вероятностью 1/n. Ожидаемое время выполнения быстрой сортировки O(n log₂n).

Пример машины Тьюринга, использующей рандомизацию.

Используем многоленточную машину Тьюринга (рис. 11.6), первая лента которой содержит вход; вторая (случайная лента) – случайную последовательность из 0 и 1, записываемых в пустые ячейки на каждом шаге работы машины; третья и т.д. ленты – рабочие.

Рис. 11.6.

Реализуем с помощью подобной машины версию быстрой сортировки.

1. Список на первой ленте заключен между маркерами и имеет длину m; используем log₂ m случайных битов второй ленты, чтобы выбрать случайное число между 1 и m.

2. Помещаем ведущий элемент на ленту 3.

3. Копируем с 1-й ленты на ленту 4 элементы, которые не больше ведущего.

4. Копируем с 1-й ленты на ленту 5 элементы, которые больше ведущего.

5. Копируем ленты 4 и 5 на ленту 1 на место входа, поместив между ними маркер.

6. Если какой-то из подсписков имеет более одного элемента, применить к нему этот же алгоритм.

Как и при реализации на компьютере, вычисление на машине Тьюринга с использованием случайных битов на второй ленте требует O(n log₂n) времени.

Язык рандомизированной машины Тьюринга.

Обычная машина Тьюринга всегда допускает некоторый язык, возможно пустой. Рандомизированная машина может вообще не допускать никакого языка. Дело в том, что каждый вход w рандомизированной машины имеет некоторую вероятность допускания, зависящую от содержимого случайной ленты, приводящего к допусканию. Поскольку исполь зуется лишь конечная часть случайной ленты, вероятность любой случайной последовательности равна 2 ^-^m, где m - число клеток случайной ленты, когда-либо просмотренных и повлиявших на переходы машины Тьюринга. Два примера дают представление о двух классах языков, допускаемых рандомизированными машинами Тьюринга.

Пример. Функция переходов рандомизированной машины M представлена на рис.11.7. Машина M не меняет символов входной ленты, а только сдвигает головки вправо (R) или остается на месте (S). Все возможные комбинации на 1-й и 2-й лентах представлены 0-й строкой таблицы (B –пустой символ); 0-й столбец – состояний машины М. Клетка qUVDE таблицы означает, что МТ M переходит в состояние q, записывает U на входной ленте и V- на случайной ленте, и сдвигает головку на входной ленте в направлении D, а на случайной ленте – в направлении E.

Рис.11.7.

Можно описать, что делает машина на входной цепочке, состоящей из 0 и 1. В начальном состоянии q₀ машина M обозревает первый случайный бит и в зависимости от его значения делает следующее:

1. Если первый случайный бит равен 0, то M проверяет - состоит w только из 0 или только из 1, в этом случае M не изменяет символы на 2-й ленте.

1.1. Если первый бит w равен 0, то M переходит в состояние q₁ и движется через все 0 вправо и останавливается, не допуская, если встретит 1, или переходит в допускающее состояние q₄, если встретит B.

1.2. Если первый бит w равен 1 и первый случайный бит равен 0, то M переходит в состояние q₂ и допускает, если все биты w равны 1.

2. Если первый случайный бит равен 1, машина M сравнивает w со вторым и последующими случайными битами, допуская, если они совпали. Таким образом, в состоянии q₀, обозревая 1 на второй ленте, M переходит в состояние q₃, сдвигая головку на случайной ленте и оставляя на месте головку на входной. В состоянии q₃ проверяет совпадение содержания обеих лент, сдвигая обе головки вправо. Если обнаруживает несовпадение, останавливается, не допуская, а если достигает пробела на входной ленте, то допускает.

Вычислим вероятность допускания входов. Для однородных входов, где встречается только один символ 0 или 1. Если вход есть 0ⁱ(i ³ 1)

- с вероятностью ½ первый случайный бит равен 0 и 0 ⁱ допускается;

- с вероятностью ½ первый случайный бит равен 1 и 0 ⁱ допускается

тогда и только тогда, когда все случайные биты, начиная со второго, равны 0. Это возможно с вероятностью 2^–ⁱ.

Суммарная вероятность допускания входа 0ⁱ есть 1/2+1/2 ×2 ^–ⁱ = 1/2+2^-(ⁱ⁺¹⁾.

Для неоднородного входа w, содержащего как 0, так и 1, вход не допускается, если первый случайный бит равен 0, допускается для первого случайного бита 1 с вероятность 2 ^–ⁱ, где i – длина входа. Общая вероятность допускания неоднородных цепочек равна 2^-(ⁱ⁺¹⁾.

Далее даны два разных определения допускания языков рандомизированными машинами.

Класс RP

Язык L класса RP допускается радомизированной машиной Тьюринга M в следующем смысле.

1. Если w не принадлежит L, то вероятность того, что M допускает w равна 0.

2. Если w принадлежит L, то вероятность того, что M допускает w не меньше ½.

3. Существует полином p(n), для которого, если w имеет длину n, то все вычисления M, независимо от содержимого случайной ленты, останавливаетсяне более, чем за p(n) шагов.

Пункты 1 и 2 определяют рандомизированную МТ типа Монте-Карло.

Рассмотренная выше рандомизированная МТ (рис.11.13), удовлетворяет условию 3, но не допускает никакого языка в смысле определения RP.

Опишем рандомизированную МТ, удовлетворяющую свойствам 1-3.

Ее вход интерпретируется как граф, и вопрос состоит в том, есть ли в этом графе треугольник, т.е. три узла, попарно соединенные ребрами. Графы с треугольниками принадлежат языку L из RP, без – не принадлежат.

Алгоритм выбирает ребро (x, y) и вершину z, отличную от x и y, случайным образом. Каждый выбор определяется просмотром новых битов на случайной ленте. Для каждой выбранной тройки x, y, z МТ проверяет, входят ли ребра (x, z) и (y, z) в граф, тогда вход содержит треугольник.

Пусть граф имеет n узлов и m ребер. Если граф имеет хотя бы один треугольник, то вероятность того, что три его узла будут выбраны в одном эксперименте, равна (3/m)(1/(n-2)), т.е. три из m ребер находятся в треугольнике, и если одно из них выбрано, то вероятность того, что будет выбран и третий узел, равна 1/(n-2). Если эксперимент повторялся k раз, то вероятность не выбрать треугольник равна 1-(1-3/m(n-2))^k.

Время работы МТ. Запись n и m не длиннее входа, k выбираем не больше квадрата длины (пропорционально n×m). В каждом эксперименте вход просматривается не более 4-х раз (чтобы выбрать ребро, а затем проверить наличие еще двух ребер), поэтому время эксперимента линейно относительно длины входа. Таким образом, до останова МТ совершает не более, чем çwô³ переходов, т.е. время работы МТ полиномиально, т.е. условие 3 выполняется.

Все три условия для языка L “графов с треугольниками” выполнены, так что L принадлежит классу RP. Также L принадлежит классу P.“

Однако найти язык из класса RP \ P значительно труднее.

Для распознавания языка L из RP существует рандомизированная машина Тьюринга типа Монте-Карло, полиномиальная по времени. Если вход w Ï L, машина не допускает, а в случае w Î L также может произойти ложный негативный исход. Так что для подтверждения допускания опыт надо провести несколько раз. Справедлива следующая теорема.

Теорема.Если L принадлежит RP, то для любой как угодно малой константы c > 0 существует полиномиальный по времени рандомизиро- ванный алгоритм, совершающий ложный негативный исход на входе

w Î L с вероятностью не больше c.

Доказательство. Для языка из L из RP допускающая его МТ допускает

цепочку из L с вероятностью, большей ½, так что, чтобы вероятность ложного негативного исхода была не больше c, необходимо повторить

проверку log₂ (1/c) раз. Поскольку время работы рандимизированной МТ полиномиально, повторение проверки не нарушит полиномиальности.“

Класс ZPP.

Второй класс языков ZPP, использующих рандомизацию, допускается машинами Тьюринга с полиномиально ограниченным ожидаемым временем работы. Время работы машины зависит от значений некоторых случайных битов, поэтому полиномиально ограниченное время работы

этих машин только ожидаемое. Машины называют МТ типа Лас-Вегас.

На входах, принадлежащих языку L=L(M), машина останавливается, допуская, в противном случае останавливается без допускания.

Легко доказать, что ZPP=co-ZPP. Достаточно переделать машину типа Лаг-Вегас, допускающую язык L в машину, допускающую язык L^’. Замкнутость класса RP относительно дополнения не очевидна, так как машины типа Монте-Карло трактуют допускание и отвергание несимметрично. Однако следующие отношения имеют место.

Теорема. ZPP = RP = co-RP.

Доказательство. 1) RP Ç co-RP Í ZPP :Пусть LÎ RP Ç co-RP, т.е. L и L^’

допускаются МТ типа Монте-Карло с полиномиально ограниченным временем. Возьмем полином, ограничивающий время работы обеих машин. Построим для L МТ M типа Лас-Вегас:

1. Сначала работает машина для L типа Монте-Карло, если она допус

кает, M допускает и останавливается.

2. Если машина для L не допускает (останавливается, не допуская), за-

пустим машину типа Монте-Карло для L^’. Если эта МТ допускает, M останавливается, не допуская. В противном случае возвращаемся к п.1.

M допускает, если вход w Î L; M отвергает w, если w Ï L. Ожидаемое время в одном цикле – 2p(n). Вероятность того, что один цикл разрешит вопрос не меньше ½. Если w Î L, то п.1 имеет вероятность ½ привести машину M к допусканию, а если w Ï L – столько же шансов привести M к отверганию. Таким образом, ожидаемое время работы машины M не больше 2p(n) + (1/2)2p(n) + (1/4)2p(n) + (1/8)p(n) +…= 4p(n).

2) ZPP Í RP Ç co-RP :Пусть L Î ZPP, тогда язык L допускается МТ M₁ типа Лас-Вегас, ожидаемое время работы которой - некоторый полином p(n). Построим для L МТ M₂ типа Монте-Карло: M₂ имитирует 2p(n) шагов работы M₁. Если M₁ допускает в течение этого времени, M₂ также допускает, в противном случае она отвергает.

Если вход w Ï L, то M₁ не допускает, если w Î L, то M₁ допустит, но время ее работы может превысить 2p(n). Гарантия, что это произойдет в пределах 2p(n) не меньше ½. Допустим противное: время работы не больше 2p(n) с вероятностью c < ½. Тогда ожидаемое время работы M₁ на входе w не меньше (1 - c)2p(n), поскольку 1 – c является вероятностью того, что M₁ надо времени больше, чем 2p(n). Но 2(1 - c) > 1, так что ожидаемое время работы M₁ больше p(n). Тогда и время допускания машины M₂не меньше ½. Таким образом построенная машина M₂ типа Монте-Карло с ограниченным временем, что доказывает принадлежность L классу RP.

Для доказательства того, что L Î co-RP - по M₁ строим МТ типа Монте-Карло с полиномиально ограниченным временем для L^’. ’

Из теоремы 11.17 следует, что ZPP Í RP. Место этих классов между P и NP определяют следующие теоремы.

Теорема.P Í ZPP.

Доказательство. Любая детерминированная полиномиально ограниченная МТ является также полиномиально ограниченной МТ типа Лас-Вегас, не использующей возможности случайных выборов. š

Теорема. RP Í NP.

Доказательство. Пусть язык L принадлежит RP. Тогда допускающая L МТ M₁ типа Монте-Карло. Можно построить НМТ M₂, моделирующую работу М₁ и, когда М₁ рассматривает случайный бит M₂ оба возможных значения этого бита записывает их на свою случайную ленту.

M₂ допускает, когда M₁ допускает, и не допускает в противном случае.

Возьмем w Î L. Поскольку M₁ имеет вероятность допускания больше ½, должна существовать последовательность битов на ее случайной ленте, приводящая к допусканию w. M₂ берет эту последовательность (угадывает) битов и также допускает. Таким образом, w Î L (M₂). Если

w Ï L, то ни одна последовательность случайных битов не приводит M₁ к допусканию, следовательно, нет и последовательности случайных битов, приводящей к допусканию M₂. Таким образом, w Ï L(M₂).

На рис.11.8 представлены соотношения между введенными классами.

Рис.11.8.

Приложения в криптографии

По стойкостью криптосистемы понимают отсутствие полиномиального алгоритма дешифрования. Здесь возникает одно существенное затруднение: современное состояние теории сложности вычислений не позволяет обосновывать сверхполиномиальные нижние оценки сложности для конкретных задач рассматриваемого класса. Поэтому идет поиск наиболее слабых достаточных условий для существования стойких схем каждого из типов. При этом различаются два направления исследования – в самой теории сложности и для конкретных теоретико-числовых задач.

Криптография и гипотеза P¹ NP

Рассмотрим следующий естественный вопрос: не является ли гипотеза

P¹ NP необходимым и достаточным условием для существования стой- ких криптографических схем? Необходимость очевидна. Что касается вопроса о достаточности, то здесь напрашивается следующий подход: выбрать какую-либо NP-полную задачу и построить на ее основе криптографическую схему, задача взлома которой была бы NP-полной. На практике оказалось, что любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательности входных слов. Дело в том, что в определении класса NP заложена мера сложности

“в худшем случае”, для стойкости же криптосистем необходима сверхполиномиальная сложность “почти всюду”. Таким образом, для криптографической стойкости необходимо существенно более сильное предпололжение, чем P¹ NP.

Теоретико-числовой подход к сложности в криптографии

Теория сложности применительно к криптографии используется следующим образом. Построение публичных ключей требует быстрого нахождения больших простых чисел. Вероятность, что n-битовое число простое, равна 1/n. Имея полиномиальный по времени относительно n алгоритм проверки простоты, мы могли бы, выбирая числа случайно, проверять их и останавливаться, обнаружив простое число. Это давало бы нам полиномиальный алгоритм типа Лас-Вегас. К сожалению такого алгоритма проверки на простоту нет, хотя и существует полиномиальный алгоритм типа Монте-Карло.

Безопасность шифрования, основанного на RSA-схеме, зависит от невозможности разложить произвольное целое число на простые множители за полиномиальное время, в частности, от невозможности разложить целое, о котором известно, что оно равно произведению двух больших простых чисел. Если бы оказалось, что множество простых или множе-

ство составных чисел образует NP-полный класс, тогда бы полиномиаль- ный алгоритм разложения числа на простые множители доказывал бы равенство N = NP, что маловероятно. С другой стороны, будет доказано, что оба языка – простых и составных чисел принадлежат NP. Они допол- няют друг друга, поэтому, если бы какой-то из них был NP-полным, то можно доказать NP = co-NP, что также вызывает сомнение. Кроме того, ввиду принадлежности языка простых чисел классу RP, NP-полнота последнего влекла бы равенство RP = NP, которое также маловероятно.

Сложность вычислений в модулярной арифметике

Модулярная арифметика используется в проверке простоты натурального числа, так что дадим некоторые оценки сложности вычислений по модулю простого числа p. Двоичное представление p занимает n битов, т.е. само p близко к 2 ⁿ, так что любое вычисление, включающее p ша- гов не полиномиально по времени, занимает время не менее O(2 ⁿ).

Сложение и умножение по модулю p требует время O(n) и O(n²), соответственно. Возведение в степень методом рекурсивного удвоения также полиномиально. Метод состоит в следующем: вычислить x ^p-1

(или другую степень до p) можно следующим образом:

1. Вычисляем (не более n степеней) x, x ², x⁴,…, пока степень не превысит p-1. Каждое значение является n-битовым числом, которое находится за время O(n²) путем возведения в квадрат предыдущего, поэтому общее время равно O(n³).

2. Найдем двоичное представление (p-1)₂= a _n-1a _n-2…a₀, или

p-1 = a ₀ + 2a₁ + 4a ₂ +…+2 ^n-1a _n-1, где каждое a _iесть 0 или 1. Тогда

_x ^p^-1₌_xa ₀ + 2a₁ + 4a₂ +…+2 ⁿ^-1a _n_-1

есть произведение степеней x²ⁱ, для которых a_i = 1. Поскольку эти степени вычислены в п.1 и являются n-битовыми, их произведение можно вычислить за время O(n³). Таким образом, все вычисление x ^p-1занимает время O(n³).

Рандомизированная полиномиальная проверка простоты.

Опишем, как применять рандомизированные алгоритмы для поиска больших простых чисел. Покажем, что язык составных чисел принадлежит RP. Метод генерации n-битовых простых чисел состоит в следующем: случайно выбирается n-битовое число и много раз применяется алгоритм Монте-Карло для распознавания составных чисел. Если некоторая проверка показала, что число составное, то число точно не простое. Если все проверки не показывают, что число составное, то вероятность, что оно составное не больше 2^-^k, где k – число проверок. Т.е. с большой долей уверенности можно сказать, что число простое, и этим обосновать безопасность криптографических операций.

Идея рандомизированного алгоритма базируется на теореме Ферма: если p – простое число, то для любого x, x ^p-1 = 1(mod p). Если p - составное, то существует x, для которого x ^p-1 ¹ 1(mod p), для не менее половины чисел из интервала [1, p-1].

Рандомизированный алгоритм типа Монте-Карло для составных чисел:

1. Выбираем случайное число x в интервале [1, p-1].

2. Вычисляем x ^p-1 (mod p). Если p n-битовое, вычисление займет время O(n³).

3. Если x ^p-1 ¹ 1(mod p), то допустим вход x, в противном случае остановимся без допускания.

Если p – простое, то x ^p-1 = 1(mod p), МТ остановится без допускания. Это одна ветвь работы машины типа Монте-Карло – если вход не принадлежит языку, то он никогда не допускается и при повторном запускании на этом входе. Для составных чисел “c” не менее половины чисел x из интервала [1, c] удовлетворяют уравнению Ферма:

x ^c-1 =1 (mod c), в частности для взаимно простых с “c”. Эти числа требуют еще одной, более сложной проверки, чтобы убедиться, что они составные.

Однако здесь не говорится о том, как разложить составное число на множители за полиномиальное время, по видимому, такого, даже рандомизированного алгоритма нет. В противном случае, криптографические методы защиты, основанные на невозможности разложить очень большие числа на простые множители за полиномиальное время оказались бы небезопасными.

Недетерминированная проверка простоты.

Здесь будет доказано, что языки простых и составных чисел принадлежат NPÇco-NP. Отсюда следует, что вероятность NP-полноты этих языков ничтожна, иначе NP = co-NP, что совершенно невероятно.

Теорема.Множество составных чисел принадлежит NP.

Доказательство. Строим недетерминированный полиномиальный алгоритм распознавания составных чисел:

1. Имея n-битовое число p, угадываем сомножитель q, состоящий не более, чем из n битов (q¹1, p).

2. Разделим p на q и проверим, что rm (p, q) = 0. Если это так, то эта часть детерминирована и может быть выполнена за время O(n²) на многоленточной МТ.

Если p - составное, то оно имеет хотя бы один сомножитель q ¹ 1, p. НМТ, угадывающая все возможные числа, содержащие не более n битов, на одной из веток угадает q. Эта ветка ведет к допусканию.

Наоборот, допускание НМТ означает, что найден делитель числа p, отличный от 1 и p. Язык описанной НМТ содержит все составные числа.

Распознавание простых чисел с помощью НМТ сложнее. Можно было угадать, что число (делитель) не является простым, но надо еще проверить, что число p действительно простое, т.е. что существует число x между 1 и p-1, имеющее порядок p-1. Значит, ни одно из чисел

x ², x ³,…,x ^p-2 не равно 1. Такая проверка потребует времени не менее

2 ⁿ для n-битового числа p. Поэтому используем факт, что для простого p порядок x по mod (p) делит p-1 (ord (x) ïp-1). Таким образом, достаточно для простых делителей q числа p-1 проверить, что x ⁽^{p-1) /}^q ¹1. Число таких проверок – O(n), поэтому все их можно выполнить с помощью полиномиального алгоритма.

Теорема. Множество простых чисел принадлежит NP.

Доказательство. Пусть p n-битовое число, не равное 1, 2, 3.

1. Угадываем список сомножителей {q₁, q₂,…,q _k}, двоичные представления которых вместе занимают не более 2n битов, и ни одно из них не имеет более n-1 битов. На каждой ветви НМТ время работы O(n).

2. Перемножаем все сомножители q_i и проверяем, равно ли их произведение p-1. Это потребует времени не более O(n²).

3. Если произведение совпало с p-1, рекурсивно проверим, что каждый сомножитель является простым.

4. Если не все сомножители q являются простыми, угадаем значение x и проверим неравенство x ⁽^{p-1) /}^q ¹ 1 для каждого q, делящего p-1. Тем самым устанавливается, что порядок x равен p-1, в противном случае порядок x должен делиться на один из множителей (p-1) / q .

Возведение в степень осуществляется описанным выше эффективным

алгоритмом, сделав не более k умножений (k< n), затратив времени

O(n³), так что общее время – O(n ⁴).

Построенный недетерминированный алгоритм полиномиален вдоль каждой ветви, кроме шага 3. Рассмотрим рекурсивное вычисление на шаге 3, представив его в виде дерева, в корне которого находится n-битовое число p, сыновьями являются угаданные сомножители числа

p-1, под каждым q _i угадываемые сомножители числа q _i –1, которые также надо проверить данной рекурсивной процедурой, и т.д. - до листьев, состоящих не более, чем из 2 бит.

Произведение сыновей меньше самого узла, тем более меньше p.

Время работы, выполняемой для узла, исключая работу в рекурсивных вызовах, оценивается как a^. (log₂i)⁴, для некоторой константы a. Верхнюю оценку для любого уровня j можно получить суммированием по узлам, и так как соответствующие узлам угаданные сомножители составляют произведение, не большее p-1, то суммы ограничены сверху a(log₂ p)⁴, что не превосходит an⁴.

Итак, время работы на каждом уровне O(n⁴), уровне не более n, общее время работы на каждой ветке O(n⁵). š