Современная прикладная криптография (стр. 12 )

Вычислительная сложность алгоритма в свою очередь измеряется его временной (T) и емкостной (S) сложностями в зависимости от размера входных данных [13]. Временная сложность - это время, затрачиваемое алгоритмом для решения задачи, рассматриваемое как функция размера задачи или меры количества входных данных (например, размером задачи умножения матриц может быть наибольший размер матриц-сомножителей). Аналогично, емкостная сложность - это объем необходимой машинной памяти. Поведение этих сложностей в пределе при увеличении размера задачи называется асимптотическими сложностями. Эти сложности алгоритма определяют в итоге размер задач, которые можно решить этим алгоритмом.

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

Теория сложности в основном имеет дело со сложностью задач в худшем случае. Однако в криптологии более важна средняя сложность задачи, а алгоритм с наименьшей сложностью в худшем случае не обязательно имеет наименьшую среднюю сложность. Например, как установлено в работах Кли и Минти, так называемый симплекс-метод для решения задач линейного программирования имеет большую (экспоненциальную) временную сложность, но в то же время этот метод хорошо работает на практике. Другой пример: алгоритмы ветвей и границ [26], успешно решающие так называемую задачу о рюкзаке (см. далее), имеют также большую (экспоненциальную) временную сложность.

Естественно, для анализа работы алгоритма нужны модели вычислительных машин, достаточно простых для анализа, но в то же время точно отражающих основные черты реальных машин. Так, в работе [13] рассматриваются модели, включающие машину с произвольным доступом к памяти, машину с произвольным доступом к памяти и хранимой программой, детерминированную и недетерминированную машину Тьюринга и др.

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

Если алгоритм обрабатывает входы размера n за время cn2, где с - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n2) (читается "порядка n2"). Точнее, неотрицательная функция g(n) есть O(f(n)) (пишут g(n)=O(f(n)), если существуют постоянные с и , для которых

g(n) c|f(n)| при .

Если g(n) = является полиномом степени m (deg g(n) = n), то g(n)=0(). Действительно, легко видеть, что

|g(n)| ||+||*n+…+ при 1.

Напомним некоторые операции с символом "большое 0". Так,

g(n) = O(g(n)); c•O(g(n)) = O(g(n)), если с = const ;

0(g(n))•0(g(n)) = O(g(n)); O(O(g(n))) = O(g(n));

O(f(n))•O(g(n)) = 0(f(n)g(n)); 0(f(n)g(n)) = f(n)0(g(n)).

Написанные равенства всегда односторонни. Так, пишется 3n2+n = 0(n2), но никогда не пишется 0(n2) = 3n2+n

Полиномиальным алгоритмом или алгоритмом полиномиальной временной сложности называется алгоритм, у которого временная сложность равна T = 0(р(n)), где р(n) - некоторый полином, а n - размер входа. Алгоритмы, временная сложность которых есть , где с = const, p(n) - полином, называются экспоненциальными.

В следующей таблице из работы [24] приведены времена для различных классов алгоритмов при n = 106 на последовательной машине, выполняющей 106 операций в секунду.

Класс Сложность алгоритма	Число операций для п=106	Реальное время
Полиномиальный	0(1)	1 11111	1 мс
Линейный Квадратичный Кубичный	0(n) 0(n2) 0(n3)		1 c 10 дней 27397 лет
Экспоненциальный	0()		лет

Задачи, которые решаются в полиномиальное время, называются решаемыми (tractable), так как они могут обычно быть решены для входа достаточно реального размера. Задачи, которые не могут быть систематически решаемыми за полиномиальное время, называют нерешаемыми (intractable), или просто трудными (hard).

Следует заметить, что существуют и алгоритмически неразрешимые задачи (undecidabie). Они настолько трудны, что невозможно создать алгоритм для их решения. Такова, например, десятая проблема Гильберта: существует ли алгоритм, решающий в целых числах уравнение = 0 для многочлена р с целыми коэффициентами. показал, что такого алгоритма в принципе не существует. Другие примеры неразрешимых задач были ранее указаны Тьюрингом.

Далее приведена классификация задач по сложности и дано наглядное возможное их соотношение друг с другом (такое соотношение неизвестно). Схема приведена по работе [24], но несколько изменена для удобства изображения.

Класс P или P-TIME (Poiyncriai) состоит из всех задач, решаемых за полиномальное время. Примеры приведены далее.

Класс NP или NP-TIME (Nondeterrlnlstic Polynomial) состоит из всех задач, решаемых за полиномиальное время на недетерминированной машине Тьюринга, способной параллельно выполнять неограниченное количество независимых вычислений. Это означает, что если вариант решения проверяется, то он может быть проверен на машине Тьюринга за полиномиальное время. Конечно, это не означает решить задачу, так как нет гарантии, что машина угадает правильное решение. Чтобы математически решать задачу из NP класса, надо, по-видимому, тратить экспоненциальное время. Примером такой задачи является "задача рюкзака" ("knapsack problem"): дано множество из n целых чисел а = {} и целое число S, требуется определить, существует ли множество чисел из а, сумма которых равна S. Ясно, что эта задача принадлежит np классу, так как для любого подмножества чисел в а легко проверить, равна ли их сумма числу s. Найти же подмножество чисел, сумма которых равна S, гораздо сложнее. Существует всего таких подмножеств (включая пустое множество), и проверка их всех имеет временную сложность T=0().

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

Класс NP включает класс P, так как любая задача, полиномиально решаемая на детерминированной машине Тьюринга, полиномиально решаема и на недетерминированной. Если бы все задачи из np-класса полиномиально решались бы на детерминированной машине, то было бы верно равенство P=NP. Хотя многие задачи из NP-класса кажутся более сложными, чем задачи из P (например, задача о рюкзаке, задача о выполнимости), но никто еще не доказал, что P NP.

Основной метод, используемый для доказательства близости задач, состоит в "сведении" их друг к другу с помощью конструктивного преобразования, которое позволяет превратить любой алгоритм решения одной задачи в алгоритм решения другой. Известно много примеров подобной сводимости [26]. В 1971 г. Кук (Cook) показал, что задача о выполнимости имеет свойство, что каждая другая задача из np может быть сведена к ней за полиномиальное время. Далее Карп (Каrр) доказал, что многие хорошо известные комбинаторные задачи, включая "задачу о коммивояжере" [15], столь же трудны, как задача о выполнимости.