Сложность вычислений

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

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

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

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

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

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

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

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

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

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

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

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

Как и при реализации на компьютере, вычисление на машине Тьюринга с использованием случайных битов на второй ленте требует 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.



Можно описать, что делает машина на входной цепочке, состоящей из 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 ^-i.

Суммарная вероятность допускания входа 0ⁱ есть 1/2+1/2 2 -ⁱ = 1/2+2^{-( i+1)}. Для неоднородного входа w, содержащего как 0, так и 1, вход не допускается, если первый случайный бит равен 0, допускается для первого случайного бита 1 с вероятность 2 -ⁱ, где i - длина входа. Общая вероятность допускания неоднородных цепочек равна 2^{-( i+1)}.

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

Класс RP

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

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

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

Существует полином 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 выбираем не больше квадрата длины (пропорционально nm). В каждом эксперименте вход просматривается не более 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 типа Лас-Вегас:

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

Если машина для 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₂).

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

Тема 5. Сложность арифметических проблем

§1. Сложность проверки простоты числа

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

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

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

Самостоятельные занятия

[3], раздел 2, глава 3.

[1] .глава 11.5.

[2], раздел 1..

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

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

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

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

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

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

_x ^{p - 1} _{= x} a₀ + 2 a₁ + 4 a₂ +…+2 ^{n - 1}a _{n -1}

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

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

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

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

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

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

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

Если 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”. Эти числа требуют еще одной, более сложной проверки, чтобы убедиться, что они составные.

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

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

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

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

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

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

Разделим 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.

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

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

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

Если не все сомножители 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⁵).

Тема 6. Приближенные алгоритмы

Самостоятельные занятия

[5], глава 7, § 37.

Приближенные алгоритмы

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

Система оценок приближенных алгоритмов:

Для оптимизационных задач можно говорить о решении с ошибкой не более, чем в (n) раз. Если C* - оптимальное решение, а C - приближенное, то должно выполняться неравенство

1 max (C/C*, C*/C) (n).

Иногда качество алгоритма оценивают через относительную ошибку

C - C* / C (n) для входа длины n.

Для некоторых задач , не зависят от длины входа n, в других случаях приходится довольствоваться алгоритмами, в которых оценка ошибки растет с ростом n.

Иногда можно улучшить качество приближения, увеличив время работы алгоритма, которое будет ограничено полиномом p(n, 1/), где n -длина входа и - оценка относительной ошибки.

Далее рассматриваются полиномиальные приближения для трех NP-полных задач с разными оценками качества приближенных алгоритмов.

Задача о вершинном покрытии

Напомним, что вершинным покрытием неориентированного графа

G = (V, E) называется множество V ' V, что для каждого ребра (u, v) графа G по крайней мере один из концов u, v принадлежит V '. Размером вершинного покрытия считается количество входящих в него вершин. Задача о вершинном покрытии состоит в нахождении оптималь ного вершинного покрытия, т.е. вершинного покрытия минимального размера. С алгоритмом AVC (рис. 37.1) можно найти вершинное покры тие, которое хуже оптимального не более чем в 2 раза.

AVG (G)

V'

E'

while E'

do возьмем произвольное ребро {u, v} из E'

C C {u, v}

удалим из E' все ребра, инцидентные u или v

return C

Работа алгоритма AVC: Из множества E', которое сначала совпадает с E, выбирается ребро (u, v) и его концы добавляем в множество V ', которое сначала пусто. После чего из E' удаляются все ребра, инци- дентные u или v. Цикл продолжается, пока E' . Время работы алгоритма O(E).

Заключение. Приложения теории сложности в практике программирования и в криптографии

Вопросы сложности вычислений лежат в основе криптографических методов Надежность шифров базируется на уверенности, что дешифро вание является труднорешаемой задачей. Так безопасность шифров, основанных на RSA-схеме, гарантируется невозможностью разложить целое, равное произведению двух больших простых чисел, за полино миальное время. Проблема принадлежит классу NP. Полной гарантией безопасности было бы принадлежность языка простых чисел или языка составных чисел к NP-полным классам, но равенство NP=co-NP сомнительно. Более того, доказано, что язык простых чисел принадлежит классу RP, так что NP-полнота языка простых чисел приводила бы к равенству RP=NP, что тоже маловероятно.

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

Перечень основной и дополнительной литературы

1. Дж. Хопкрофт, Рад. Мотвани, Дж. Ульман. Введение в теорию автоматов, языков и вычислений. Пер.с англ.-М.: Издательский дом “Вильямс”,2002

2. А.В. Черемушкин. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002.

3. А.Н. Гамова. Математическая логика и теория алгоритмов. Учебное пособие. Изд-во СГУ,3-е изд., дополненное. Саратов, 2005.

4. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

5. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.- М.: МЦНМО, 2001.

6. Н. Катленд. Вычислимость. Введение в теорию вычислимых функций: Пер.с англ.- М.: Мир,1983.

7. Н. Вирт. Алгоритмы и структуры данных: Пер.с англ.- СПб.: Невский Диалект, 2001.

8. Т.А. Павловская. С/C⁺⁺.Программирование на языке высокого уровня.- СПб.: Питер, 2002.

9. Г.С. Иванова, Т.Н. Ничушкина, Е.К. Пугачев. Объектно-ориентированное программирование. М.: Изд-во МГТУ имени Н.Э.Баумана,2000

Размещено на Allbest.ru

...