Элементы теории сложности

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

Алгоритмом называют определенный вычислительный процесс, который принимает переменные на входе и возвращает на выходе.

Разумеется, вышеприведенное определение – это интуитивное понятие. Строго алгоритм определяется через такие конструкции как машина Тьюринга, рекурсивные функции или нормальный автомат Маркова. Изоморфизм указанных конструкций доказан теоремами Дятлова, Маркова и Тьюринга. Предположение об эквивалентности интуитивного понятия алгоритма и машины Тьюринга выражается гипотезой Тьюринга, рекурсивных функций – тезисом Чёрча, НАМ – принципом нормальности.

Алгоритм описывает некоторую последовательность действий, выполняемых над данными входа определенного размера с тем, чтобы получить некоторые данные на выходе. Разумеется, время работы алгоритма и объем памяти, необходимой для вычислений, зависят от того, какого размера была информация на входе (действительно, сложить два однозначных числа гораздо проще, чем два десятизначных). Однако данные, поступающие на вход разных алгоритмов, могут иметь разный характер. Это могут быть целые или вещественные числа, логические переменные, строки символов и т.п. Для того, чтобы сравнивать зависимость времени работы от размера входа у разных алгоритмов, вводят следующую формализацию:

Размером входа называют число бит, необходимых для двоичного представления входных данных в соответствующей кодировке.

Иногда для простоты указывают не точное, а приблизительное количество необходимых бит. Например, для представления целого положительного числа n необходимо +1 бит, но обычно это значение заменяется log n.

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

Максимальным временем работы алгоритма называют верхнюю оценку времени работы для всевозможных входов определенного размера. Максимальное время работы алгоритма выражается как функция от размера входа.

Пример.

Рассмотрим алгоритм умножения двух чисел a и b «в столбик», и пусть числа на входе будут двоичными трехзначными.

Очевидно, самое большое время работы получится, если a=b=111:

_× 1 1 1

1 1 1

₊ 1 1 1

₊ 1 1 1

1 1 1___

1 1 0 0 01

В этом случае потребовалось 6 битовых операций сложения, или 2 сложения трехбитовых чисел.

Но при другом входе этот же алгоритм потребует меньшего времени. Например, пусть a=101, b=110. В таком случае

_× 1 0 1

1 1 0

₊ 1 0 1

1 0 1

1 1 1 1 0

Потребовалось всего 2 битовых операции сложения, или одно сложение трехбитовых чисел.

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

В случае, когда длина размер входа составляет r бит, максимальное время работы данного алгоритма составляет (r—1)(r+1) ≈ r² битовых сложений, или, если выражать максимальное время работы как функцию от значения множителей n, log² n.

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

(a+b) mod n, (a—b) mod n O(log n);

ab mod n, a^-1 mod n O(log² n);

a^b mod n O(log³ n);

O(log² n).

Средним временем работы алгоритма называется среднее время работы для всех входов одинакового размера и выражается как функция от размера входа.

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

Зачастую время работы алгоритма представляет собой весьма сложную по своему виду функцию, поэтому время работы представляют приблизительно. В примере, приведенном выше, мы приблизили время работы (r—1)(r+1) значением r².

Для исследования алгоритмов важным является не точное время работы, а характер возрастания времени работы в зависимости от размера входа. Как правило, сложность алгоритма исследуется в асимптотике, то есть при размере входа n>n₀ для некоторого n₀, поэтому широко используются такие конструкции как O(g(n)), o(g(n)).

Вычисляя пределы соотношений при n→∞, 0 < є < 1 < c, убедимся, что в асимптотике (для n>n₀ для некоторого n₀) выполняются соотношения:

1 < ln ln n < ln n < exp( ) < n^є < c^{ln n} < n^c < n^{ln n} < cⁿ < nⁿ < .

Будем говорить, что алгоритм обладает полиномиальной сложностью (по времени), если время его работы составляет O(n^k), то есть может быть ограничено сверху многочленом степени k для n>n₀ при некотором n₀.

Алгоритм, время работы которого составляет e^o(n), обладает субэкспоненциальной сложностью.

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

Полиномиальные по времени алгоритмы считаются эффективными, а задачи, решаемые такими алгоритмами, объединены в класс P.

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

Важным примером субэкспоненциальной функции является

L_q[α,c]=O(exp((c+o(1))ln^αq(ln ln q)^1-α)),

где c > 0, 0 < α < 1, q – длина входа.

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

В криптографии для создания двухключевых криптосистем используются такие проблемы, прямая задача для которых относится к классу полиномиальных (по времени), а обратная задача имеет только экспоненциальные или субэкспоненциальные алгоритмы решения.

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

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