Теория вычислительной сложности

 
 
 
 
 
 
 
 
 
 
 
 
 
Г.П. Агибалов  
 
ТЕОРИЯ  
ВЫЧИСЛИТЕЛЬНОЙ 
СЛОЖНОСТИ 
 
Учебное пособие 

Министерство науки и высшего образования
Российской Федерации
Томский государственный университет

Г. П. Агибалов

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

Учебное пособие

Томск
2018

УДК 519.7
ББК 22.13я7

Агибалов Г. П. Теория вычислительной сложности: учеб.
пособие. — Томск: Издательский Дом Томского государственного
университета, 2018. — 42 с.

ISBN 978-5-94621-768-2

Пособие представляет собой курс лекций с тем же названием,
прочитанный автором в 2016/17 и 2017/18 учебных годах студентам кафедры защиты информации и криптографии по специальности «Компьютерная безопасность». Знакомство с курсом предполагает знание студентами основ дискретной математики и начальных понятий алгебры, теории алгоритмов и математической
логики.

УДК 519.7
ББК 22.13я7

c⃝ Г.П. Агибалов, 2018
c⃝ Томский государственный
ISBN 978-5-94621-768-2
университет, 2018

Предисловие
Теория вычислительной сложности (ТВС) — это наука о
сложности алгоритмов. Есть много книг о ней, в том числе исчерпывающего содержания. Наше учебное пособие этим свойством
не обладает и не претендует на полное изложение ТВС в её современном состоянии. Оно не рассчитано и на профессиональных специалистов по теории вычислительной сложности. Даже
название пособия не отражает его содержания. Оно просто повторяет название 36-часового курса лекций из образовательной
программы Томского государственного университета по специальности Компьютерная безопасность. Его цель — дать студентам этой специальности начальные понятия из теории временн´ой
сложности алгоритмов и важнейшие результаты из теории разрешимости алгоритмических задач в худшем и типичном случаях,
включая теоремы о NP-полноте задачи выполнимости, о генерической разрешимости задачи останова машины Тьюринга и о
генерической сложности задачи дискретного логарифмирования.

С благодарностью

Валентине Владимировне Быковой — за материал по асимптотическим оценкам сложности и основным сложностным классам алгоритмов;
Александру Николаевичу Рыбалову — за материал по генерической сложности алгоритмов;
Ирине Анатольевне Панкратовой — за редактирование и подготовку рукописи лекций к публикации в данном формате.

Геннадий Петрович Агибалов
01.09.2018

3

1. Сложность алгоритмов
Сложность алгоритма — одна из мер его качества, а именно, мера эффективности алгоритма. К примеру, другой мерой
качества алгоритма служит его точность. По любой мере качества можно сравнивать различные алгоритмы, решающие одну
и ту же задачу. Можно говорить, например, что один алгоритм
эффективнее другого, который, в свою очередь, точнее первого,
т. е. первый алгоритм имеет меньшую сложность, но второй более
точный — доставляемое им решение задачи в каком-либо смысле (по значению, по расстоянию) ближе к истинному решению
и т. п. Здесь и далее под задачей понимается то, что в английском языке называется problem, а в русском иногда — массовой
проблемой, или множеством экземпляров проблемы, решаемых
одним и тем же алгоритмом.
Понятие сложности алгоритма предполагает наличие у решаемой им задачи числовой характеристики, называемой размером
задачи и являющейся в действительности размером входных данных (или, как говорят, входа) алгоритма, выражающим фактически меру их количества. Например, размером задачи сравнения
слов служит наибольшая длина сравниваемых слов. Размером
задачи умножения чисел в какой-либо системе счисления является наибольшее количество знаков в числе-сомножителе, представленном в этой системе. Аналогично, размером задачи умножения матриц может быть наибольший размер матрицы, участвующей в умножении. Количество рёбер в графе или слагаемых
в АНФ булевой функции может служить размером задачи о графах или булевых функциях соответственно.
Время, рассматриваемое как некоторая функция t(n) от размера n задачи и затрачиваемое некоторым алгоритмом A на решение этой задачи, называется временн`ой сложностью алгоритма A. По определению, t(n) — это число единиц времени, требуемое алгоритму A для обработки входа размера n. Поскольку это
число может зависеть не только от размера входных данных, но и
от их значения, допускают некоторые разновидности временной
сложности алгоритмов, в том числе сложность в среднем, сложность в худшем случае, сложность в типичном случае и др. Вре
менная сложность алгоритма в среднем — это t(n) =
1

|In|
i∈In
ti —

4

результат усреднения времени ti, требуемого алгоритму на обработку входа i, на множестве In всех входных данных размера n. Временная сложность алгоритма в худшем случае — это
t(n) = max
i∈In ti. Временная сложность алгоритмов в типичном слу
чае, или на большинстве входов, называемая также генерической
сложностью, определяется и рассматривается отдельно в последнем разделе. До того всюду под временной сложностью и под t(n)
подразумевается временная сложность алгоритма в худшем случае. Предел этой функции lim
n→∞ t(n), если он существует, называется асимптотической временной сложностью алгоритма A.
Аналогично определяются ёмкостная сложность алгоритма
и её разновидности. При этом под ёмкостью подразумевается размер памяти, затрачиваемой алгоритмом для представления (записи, хранения) входных, выходных и промежуточных данных
в процессе решения задачи.
Можно говорить также и о так называемой параметрической
временной (или ёмкостной) сложности алгоритма и о её разновидностях в разных случаях, понимая под нею временную (или
соответственно ёмкостную) его сложность, зависящую от размеров входов двух разных типов — информационного (n) и параметрического (k), и оцениваемую в каждом рассматриваемом
случае в зависимости только от первого при фиксированном значении второго. Например, в алгоритмах на графах в роли первого может выступать число вершин или рёбер в графе, а в роли второго — степень вершины, диаметр графа и т. п.; в алгоритмах на булевых функциях n — это число переменных, а k — это
степень нелинейности, мощность линеаризационного множества,
количество мономов в АНФ; в криптосистемах шифрования n —
это размер шифруемого текста, k — размер ключа, на котором
производится зашифрование, и др. Но об этом — в другой раз и
в другом месте.
В случае, если алгоритм представлен на некотором алгоритмическом языке, в качестве синонима временной сложности алгоритма употребляют его вычислительную сложность, понимаемую как количество операций этого языка, выраженное некоторой функцией от размера задачи, которые алгоритм выполняет, решая задачу (каждая операция считается столько раз,
сколько раз она выполняется). Говорят также и об асимптоти
5

ческой вычислительной сложности. Ёмкостная сложность алгоритма в этом случае определяется как сумма размеров памяти, требуемой алгоритмом для выполнения всех операций языка
в нём.
В частности, если алгоритм описывается как машина Тьюринга (далее МТ), то говорят, что МТ M имеет временную сложность t(n), если на любом её входе длины n она делает не более t(n) переходов и останавливается.
Приведём пример из [1, с. 12–13], демонстрирущий тот факт,
что для увеличения размера решаемой задачи важнее не увеличение скорости работы компьютера, а уменьшение временной сложности алгоритма решения этой задачи. Предположим,
что единицей измерения времени является одна миллисекунда.
Тогда максимальный размер задачи, решаемый за 1 с алгоритмами с временной сложностью n3 и n, равен соответственно 10
и 1000 = 103, т. е. замена первого алгоритма (с большей временной сложностью) более быстрым вторым алгоритмом увеличивает размер решаемой задачи в 100 раз, в то время как повышение
скорости компьютера в 10 раз увеличивает максимальный размер задачи, решаемой первым алгоритмом за то же время, только в 2,15 раза. Различие становится более значительным, если
сравнение делается на большем промежутке рабочего времени.

2. Асимптотические оценки сложности алгоритмов
Под асимптотической оценкой сложности t(n) понимается
некоторая неотрицательная вещественная функция s(n), имеющая несложное (арифметическое) выражение через n, поведение
(порядок роста) которой с ростом n (при n → ∞) совпадает, возможно, с какой-то точностью с ростом функции t(n), за исключением значений коэффициентов и аддитивных членов неглавных
порядков в ней. В этом разделе мы рассмотрим возможные разновидности таких оценок — сверху, снизу, точные. Для упроще
ния записи обозначим d(n) = t(n)

s(n) и lim = lim
n→∞ d(n), если этот
предел существует.
Будем говорить, что t(n) меньше функции s(n) по порядку роста, и писать t(n) ≺ s(n), или t(n) = o(s(n)), если lim = 0. В этом
случае s(n) называется o-оценкой функции t(n). В частности, за
6

пись t(n) = o(1) означает, что t(n) стремится к 0, становясь сколь
угодно малой, при n → ∞.
В случае lim = c > 0 говорят, что функции t(n) и s(n) асимптотически пропорциональны, или имеют один и тот же порядок роста, и пишут t(n) = O∗(s(n)), или t(n) ∼ cs(n). В этом
случае s(n) называется O∗-оценкой функции t(n). В частности,
если t(n) = O∗(1), то t(n) называют асимптотической константой. В случае c = 1, т. е. когда t(n) ∼ s(n), говорят, что t(n)
эквивалентна, или асимптотически равна, функции s(n).
Говорят, что функция t(n) не больше функции s(n) по порядку
роста, и пишут t(n) = O(s(n)), или t(n) ≼ s(n), если их отношение d(n) ограничено сверху, т. е. существуют такие натуральное
число n0 и константа c1 > 0, что для всех n ⩾ n0 имеет место
неравенство d(n) ⩽ c1. В этом случае s(n) называют асимптотической верхней оценкой, или O-оценкой для t(n).
Двойственным образом определяется асмптотическая нижняя оценка для t(n), а именно: если отношение d(n) ограничено
снизу, т. е. существуют такие натуральное число n0 и константа
c2 > 0, что для всех n ⩾ n0 имеет место неравенство d(n) ⩾ c2,
то говорят, что t(n) не меньше функции s(n) по порядку роста,
и пишут t(n) = Ω(s(n)), или s(n) ≼ t(n). В этом случае s(n)
называется Ω-оценкой функции t(n).
Наконец, если отношение d(n) функций t(n) и s(n) ограничено
одновременно и сверху и снизу, т. е. c2 ⩽ d(n) ⩽ c1 для некоторых
c1 > 0 и c2 > 0, то пишут t(n) = Θ(s(n)), или t(n) ≍ s(n), говорят,
что t(n) равна функции s(n) по порядку роста, и называют s(n)
асимптотически точной оценкой, или Θ-оценкой функции t(n).
Следует заметить, что если предел lim
n→∞ d(n) = c > 0 существует

и, следовательно, существует O∗−оценка функции t(n), то эта
оценка совпадает c Θ-оценкой для t(n) и также является асимптотически точной оценкой для t(n), т. е. t(n) ≍ s(n). Что касается Θ-оценки, то она может существовать и без существования
O∗-оценки.
Получение именно асимптотически точных оценок желательно для функций сложности алгоритмов. Когда этого не удаётся
сделать, строят асимптотические оценки других видов.
Остановимся на некоторых свойствах оценок o, O∗, O, Ω, Θ,
вытекающих непосредственно из их определений и являющихся

7

фактически свойствами соответствующих бинарных отношений
≺, ∼, ⪯, ⪰, ≍. Пусть далее t(n), s(n), s1(n), s2(n) и u(n) — неотрицательные вещественные функции, не обращающиеся в 0, по
крайней мере, для n ⩾ n0.
1. Свойства эквивалентности:
1) рефлексивность — s(n) = ϕ(s(n)) для ϕ ∈ {O∗, O, Ω, Θ};
2) симметричность — t(n) = ϕ(s(n)) ⇒ s(n) = ϕ(t(n)) для
ϕ ∈ {O∗, Θ};

3) транзитивность —
t(n) = ϕ(s(n)) & s(n) = ϕ(u(n))
⇒
⇒
t(n) = ϕ(u(n))
для всех ϕ ∈ {o, O∗, O, Ω, Θ}.
2. Свойства включения:
1) t(n) = o(s(n)) ⇒ t(n) = O(s(n)), обратное неверно;
2) t(n) = Θ(s(n)) ⇔
t(n) = O(s(n)) & t(n) = Ω(s(n))
;

3) t(n) = O(s(n)) ⇒ s(n) = Ω(t(n));
4) t(n) = Ω(s(n)) ⇒ s(n) = O(t(n));
5) t(n) = O∗(s(n)) ⇒ t(n) = Θ(s(n)).
3. Правила арифметических операций для ϕ ∈ {O, Θ}:
1) правило суммы —
t(n) = ϕ(s1(n)) & u(n) = ϕ(s2(n)) &
& s2(n) ≺ s1(n)
⇒
t(n) + u(n) = ϕ(s1(n))
; в частности,
ϕ(t(n) + c) = ϕ(t(n)) для любой константы c > 0;

2) правило произведения —
t(n) = ϕ(s1(n)) & u(n) = ϕ(s2(n))
⇒
⇒
t(n) · u(n) = ϕ(s1(n) · s2(n))
; в частности, t(n) · c =
= ϕ(t(n)) для любой константы c > 0.

3. Основные сложностные классы алгоритмов
Пусть t1(n) и t2(n) суть функции сложности алгоритмов A1
и A2 соответственно. Считают, что алгоритм A1 асимптотически быстрее алгоритма A2, если t1(n) ≺ t2(n), т. е. t1(n) =
= o(t2(n)); алгоритм A1 асимптотически не медленнее алгоритма A2, если t1(n) ≼ t2(n), т. е. t1(n) = O(t2(n)); алгоритм A1
асимптотически не быстрее алгоритма A2, если t2(n) ≼ t1(n),
т. е. t1(n) = Ω(t2(n)); наконец, алгоритмы A1 и A2 одной асимптотической сложности, или асимптотически равнозначны по
сложности, если t1(n) ≍ t2(n), т. е. t1(n) = Θ(t2(n)).
В анализе конкретного алгоритма всегда стремятся получить асимптотически точную оценку его сложности — Θ-оценку.
В случае неудачи ограничиваются обычно O-оценкой. В классификации алгоритмов по вычислительной сложности важную

8