Глава 7 Сводимость

В этой главе мы рассматриваем только временную сложность алго­ритмов и считаем, что размер входа — это неотрицательное целое число.

§ 28. Линейная сводимость

Ниже в сопоставляемых друг с другом вычислительных задачах под­разумеваются преобразования каких-то математических объектов, представляемых одинаково для всех задач, участвующих в сопостав­лении. Размер входа для алгоритмов решения рассматриваемых задач тоже должен определяться единообразно. При сравнительном иссле­довании задач затраты на выполнение вычислений измеряются ко­личеством операций из одного и того же набора (например, арифме­тических операций, битовых операций и т.д.).

Определение 28.1. Пусть Р и Q—две вычислительные задачи. Если любому алгоритму A_Q решения задачи Q можно сопоставить такой алгоритм А_Р решения задачи Р, что

Г, {п) = 0{Т_А (п)), (28.1)

то говорят, что задача Р линейно сводится к задаче Q, и пишут P^Q. В специально оговариваемых случаях утверждение Р ^ Q предполага­ет, что рассматриваются лишь такие алгоритмы A_Q, сложности кото­рых удовлетворяют некоторым фиксированным условиям.

Слово «линейно» в этом определении означает лишь то, что слож­ность получаемого алгоритма А_Р не является, скажем, квадратом, ку­бом и т.д. сложности алгоритма A_Q. Возможное присутствие условий (ограничений) на сложности алгоритмов решения задачи Q облегча­ет или просто делает возможным доказательство (28.1). В то же вре­мя, предполагается, что эти ограничения отсекают нерациональные алгоритмы; тогда смысл отношения Р ^ Q состоит в том, что каж-

186

Глава 7. Сводимость

дому приемлемому («хорошему») алгоритму решения задачи Q мы можем сопоставить алгоритм решения задачи Р такой, что выполне­но (28.1).

Пример 28.1. Будем рассматривать задачи умножения М и возве­дения в квадрат S неотрицательных целых чисел, заданных в двоич­ной системе, считая размером входа в первой задаче максимальную из битовых длин чисел п₁,п₂, а во второй — битовую длину данного числа п (будем обозначать этот размер через т), в качестве затрат будем рассматривать битовые затраты.

Из равенства п² = п-п следует, что S^M, так как это равенство дает требуемый определением 28.1 алгоритм. Дает ли равенство

(n1 + n2⁾²-n²¹-n²² п₁-п₂ = 2 ^; (28.2)

основание считать, что М ^S? Битовая длина числа п₁ + п₂ может оказаться равной т + 1. Если бы для возведения в квадрат исполь­зовался некоторый чрезвычайно нерациональный алгоритм, имею­щий, скажем, сложность m!, то соответствующий алгоритм умноже­ния имел бы сложность порядка (т + 1)!. Легко видеть, что равенство (т + 1)! = 0(т!) места не имеет. Можно пытаться определить умно­жение через возведение в квадрат как-то иначе, но можно и не отка­зываться от формулы (28.2): при установлении линейной сводимости обычно считается, что сложность любого приемлемого алгоритма вы­полнения какой-либо мультипликативной арифметической операции (умножения, возведения в квадрат, деления и т.д.) удовлетворяет, хо­тя бы для всех достаточно больших т, условиям

1. Т(т)^т,

1. Т(т) не убывает при возрастании т,

1. Г(2т) «S 4Г(т)

(условие 3 отсекает алгоритмы умножения, сложность которых растет быстрее чем т²). Приняв, что сложность алгоритма A_s удовлетворяет этим условиям, мы имеем

Т_А (т + 1) «S Т_А (2т) «S 4Т_А (т),

что дает Т_А (m) = 0(T_A (т)) для описанного с помощью (28.2) алго-ритма умножения. Мы используем здесь то, что операции вычитания и деления на 2 имеют сложность 0(т), и то, что Т_А (т) ^ т по усло-

вию 1.

Таким образом, если принимаются ограничения 1—3 для сложно­стей алгоритмов решения задачи S, то М ^ S.