Сложность алгоритмов
(расширяемое эссе)

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

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

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

(областью изменения как аргумента функций и является множество значений размера ).

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

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

Один из очевидных алгоритмов проверки простоты данного целого , который мы будем называть алгоритмом пробных делений, состоит в выяснении того, имеется ли среди целых чисел, больших единицы и не превосходящих , хотя бы одно, делящее . Количество проверок делимости на те или иные целые числа (для краткости можно говорить о “числе делений") колеблется от до (здесь — целая часть числа). Обозначив этот алгоритм буквами TD (от английских слов trial divisions — пробные деления) и приняв за размер входа само число , мы можем сказать, что для любых значение не превосходит , и найдутся сколь угодно большие , для которых это значение равно . Очевидно, что значения функции ограничены небольшой константой.

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

На выполнение любой сортировки с помощью сравнений сами значения элементов не оказывают никакого влияния, важен лишь их относительный порядок. Поэтому можно считать, что теми массивами длины , к которым применяются алгоритмы сортировки, служат перестановки чисел . Для каждого мы можем рассмотреть множество перестановок чисел , приписав вероятность каждой из них. Это дает возможность рассматривать сложность в среднем алгоритмов сортировки. Можно доказать, что для сложности по числу сравнений алгоритма QS быстрой сортировки выполнено . Сложность в среднем этого алгоритма по числу перемещений не превосходит , где — небольшая константа. Пространственная сложность ограничена константой. (Дополнительно используется стек отложенных заданий, в который, однако, попадают не сами элементы, а их индексы.)

Для любого алгоритма при любом распределении вероятностей на множестве , сложность в среднем не превосходит сложности в худшем случае: , .

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

С. А. Абрамов. Лекции о сложности алгоритмов. Изд-во МЦНМО, М., 2009 (§§5–8, приложение A).

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

Первая из них является асимптотической верхней оценкой: в соответствии с известным из математического анализа определением

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

Функции и имеют одинаковый порядок (пишут ) тогда и только тогда, когда найдутся положительные такие, что неравенства

выполнены для всех .

Например, из

сразу следует, что . Но дополнительно можно показать, что и : следствием формулы Стирлинга является оценка

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

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

Оценка вида (или ) подходит для того, чтобы “похвалить” алгоритм , т.е. охарактеризовать его сложность как достаточно низкую, но не для того, чтобы “раскритиковать” его — для таких целей скорее подойдет оценка вида .

Оценки вида , , соединяющие в себе оценки и , или же   и , в соответствующих ситуациях подходят и для характеризации сложности как сравнительно низкой, и, наоборот, как сравнительно высокой.

С. А. Абрамов. Лекции о сложности алгоритмов. Изд-во МЦНМО, М., 2009 (§§2–3).

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

Как правило, для алгоритмов сортировки рассматривается две временных сложности — по числу сравнений и по числу перемещений элементов массива. Обе они являются алгебраическими сложностями. Заметим, что по величине они могут существенно отличаться друг от друга: среди сортировок с квадратичной сложностью по числу сравнений сортировка выбором обладает чрезвычайно низкой сложностью по числу перемещений, а именно сложностью, равной (имеются в виду сложности в худшем случае).

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

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

Битовая  временная сложность получается при рассмотрении числа битовых операций в качестве функции затрат. Аналогично могут быть определены пространственные алгебраическая и соответственно битовая сложности по числу величин рассматриваемого типа. Например, если речь идет об умножении двух целых неотрицательных чисел и , то алгебраическая сложность по числу собственно умножений есть 1 независимо от того, что взято за размер входа. Но если речь идет о битовой сложности алгоритма умножения “столбиком” в худшем случае, и за размер входа взято — битовая длина (количество цифр в двоичной записи) большего из чисел, то эта сложность есть .

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

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

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

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

Быстрая сортировка имеет сложность в предположении, что все относительные порядки элементов в исходном массиве равновероятны (см. п. 2). Последнее предположение в каких-то ситуациях может быть безосновательным, — массив может быть, например, “почти упорядоченным” по построению. Но если на всех этапах разбиения в этом алгоритме сортировки разбивающие элементы выбирать случайно с соответствующей вероятностью, то такой рандомизированный алгоритм быстрой сортировки и без предположения о равновероятности всех относительных порядков элементов будет иметь сложность .

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

Правомерен и такой подход к рандомизированным алгоритмам, при котором каждому возможному входу сопоставляется вероятностное пространство обычных детерминированных алгоритмов. Такой подход используется в книге R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995, которая содержит обширный материал по рандомизации. Но можно заметить, что каждый сценарий — это в определенном смысле и есть детерминированный алгоритм. Различие между этими подходами — терминологическое.

С. А. Абрамов. Лекции о сложности алгоритмов. Изд-во МЦНМО, М., 2009 (§8).

Иногда предполагается, что вычисления проводятся некоторой машиной, память которой состоит из ячеек. При этом общее число ячеек считается бесконечным, что, разумеется, является чистой абстракцией. Поместив в ячейку результат каких-то вычислений или считав содержимое некоторой ячейки, машина обращается еще к какой-то ячейке и т.д. Относительно этого процесса предполагается, что сам переход от ячейки к ячейке не связан с какими-либо затратами. Этот принцип лежит в основе модели вычислений, называемой РАМ, что расшифровывается как “равнодоступная адресная машина” — довольно неуклюжий, но принятый термин; имеется в виду машина с равнодоступными ячейками памяти; в литературе на английском языке это RAM (random-access machine).

Модель РАМ существенно отличается в этом смысле от другой известной модели вычислений — машины Тьюринга (МТ), где время перехода от одной ячейки ленты к другой зависит от расстояния между ячейками.

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

“Алгоритма сложность”, Математическая энциклопедия, т. 1. М: Изд. “Советская энциклопедия”, 1977.

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

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

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

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

[ ]

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

← ⇐

Можно также показать, что является нижней границей сложности как в худшем случае, так и в среднем алгоритмов сортировки массивов, состоящих из попарно различных чисел, с помощью сравнений (сложность в среднем здесь предполагает, что все относительные порядки элементов в исходном массиве имеют одинаковую вероятность ). В связи с последним примером заметим, что в силу формулы Стирлинга . С. А. Абрамов. Лекции о сложности алгоритмов. Изд-во МЦНМО, М., 2009 (§§16, 17).

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

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

[ ]

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

← ⇐

Тривиальный алгоритм выбора наименьшего элемента в числовом массиве, требующий сравнений, является оптимальным в классе алгоритмов поиска наименьшего элемента числового массива длины . Все алгоритмы сортировки массивов, состоящих из попарно различных чисел, с помощью сравнений, имеющие сложность по числу сравнений, являются оптимальными по порядку сложности, и их сложность есть . С. А. Абрамов. Лекции о сложности алгоритмов. Изд-во МЦНМО, М., 2009 (§§15, 17).

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

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

Нередко бывает очень трудно ответить на вопрос о существовании в данном классе алгоритма такого, сложность которого растет с увеличением размера входа “не слишком быстро”, особенно когда неизвестна сколь-либо нетривиальная нижняя граница для сложностей алгоритмов класса. Например, в начале 60-х годов прошлого века таким был вопрос о существовании алгоритма умножения целых чисел, сложность которого по числу битовых операций растет медленнее, чем , где — битовая длина (количество цифр двоичной записи) большего из двух перемножаемых чисел. В 1962 г. А.А.Карацуба нашел алгоритм, имеющий сложность (при этом ). Затем в 1963 г., обобщая идею Карацубы и привлекая интерполяцию, А.Л.Тоом показал, что для каждого существует алгоритм умножения со сложностью ; более полно — для любого целого существует алгоритм умножения со сложностью , где . В 1972 г. А.Шенхаге и Ф.Штрассен, используя специальный вид интерполяции — так называемое быстрое преобразование Фурье, предложили алгоритм со сложностью ; если в связи с этим алгоритмом рассматривать только вида , то символ в приведенной оценке сложности можно заменить на . Наконец, в 2007 г. М.Фюрер опубликовал алгоритм со сложностью , где — некоторая функция, растущая медленнее, чем и, более того, медленнее, чем любой повторный логарифм. Неясно, как далеко можно еще продвинуться в этом направлении, в частности, неясно, возможен ли алгоритм умножения, имеющий сложность .

Нередко бывает очень трудно ответить на вопрос о существовании в данном классе алгоритма такого, сложность которого растет с увеличением размера входа “не слишком быстро”, особенно когда неизвестна сколь-либо нетривиальная нижняя граница для сложностей алгоритмов класса. Например, в начале 60-х годов прошлого века таким был вопрос о существовании алгоритма умножения целых чисел, сложность которого по числу битовых операций растет медленнее, чем , где — битовая длина (количество цифр двоичной записи) большего из двух перемножаемых чисел. В 1962 г. А.А.Карацуба нашел алгоритм, имеющий сложность (при этом ): А. А. Карацуба, Ю.П.Офман. Умножение многозначных чисел на автоматах. Докл. АH СССР, 1962, т. 145, No 2, с. 293–294, А. А. Карацуба. Сложность вычислений. Труды Математического института РАH, 1995, т. 211. с. 186–203.

Затем в 1963 г., обобщая идею Карацубы и привлекая интерполяцию, А.Л.Тоом показал, что для каждого существует алгоритм умножения со сложностью ; более полно — для любого целого существует алгоритм умножения со сложностью , где : А. Л. Тоом. О сложности схемы из функциональных элементов, реализующей умножение целых чисел. Докл. АH СССР, 1963, т. 150, No 2, с. 496–498.

В 1972 г. А.Шенхаге и Ф.Штрассен, используя специальный вид интерполяции — так называемое быстрое преобразование Фурье, предложили алгоритм со сложностью ; если в связи с этим алгоритмом рассматривать только вида , то символ в приведенной оценке сложности можно заменить на , — см. раздел 8.10 в книге А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

Наконец, в 2007 г. М.Фюрер опубликовал алгоритм со сложностью , где — некоторая функция, растущая медленнее, чем и, более того, медленнее, чем любой повторный логарифм: М. Fürer. Faster Integer Multiplication. Proceedings of the 39th ACM STOC 2007 conference, pp. 57–66, 2007. М. Fürer. Faster Integer Multiplication Algorithm. SIAM J. Comp. 39, 3, pp. 979–1005, 2009.

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

Подробный обзор упомянутых алгоритмов можно найти в разделе 2.7 (“Быстрые алгоритмы умножения и деления целых чисел") книги О. Н. Герман, Ю. В. Нестеренко. Теоретико-числовые методы в криптографии. М: Издательский центр “Академия”, 2012.

К этому добавим, что сложность по числу арифметических операций алгоритма Штрассена (1969 г.) перемножения двух числовых матриц порядка допускает оценку , в то время, как алгоритм, непосредственно следующий из определения произведения матриц, имеет сложность (при этом ). Используя другие идеи, Д. Копперсмит и С. Виноград в 1987 г. предложили алгоритм со сложностью , где — порядок перемножаемых квадратных матриц. Этот результат остается рекордным по сей день. Существует ли для любого алгоритм умножения матриц со сложностью — это открытый вопрос.

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

Например, в настоящее время известен полиномиальный алгоритм проверки простоты натуральных чисел с битовой сложностью , где за размер входа принимается битовая длина входного числа; алгоритм опубликован в 2004 г. М.Агравалом, Н.Кайалом и Н.Саксеной. (При таком размере входа сложность тривиального алгоритма TD (см. п.1), притом даже не битовая, а по числу делений, есть .)

Например, в настоящее время известен полиномиальный алгоритм проверки простоты натуральных чисел с битовой сложностью , где за размер входа принимается битовая длина входного числа; алгоритм опубликован в 2004 г. М.Агравалом, Н.Кайалом и Н.Саксеной: M. Agrawal, N. Kayal, N. Saxena. PRIMES is in P. Annals of Mathematics, (2), Vol. 160, No 2, 2004, pp. 781 – 793. (При таком размере входа сложность тривиального алгоритма TD (см. п. 1), притом даже не битовая, а по числу делений, есть .)

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

В частности, остается много неясного относительно полиномиальных алгоритмов для задач распознавания, где ответ — это одно из слов “да”, “нет” или же одно из чисел 1, 0 и т.д.

В этой связи рассмотрим класс задач NP. Все задачи этого класса могут интерпретироваться как задачи проверки существования какого-то математического объекта , представляемого, как и исходный объект , конечной последовательностью символов, т.е. словом в некотором алфавите . Длину слов и обозначим через и . Размер входа — это , затраты измеряются числом операций над символами (по аналогии с битовыми операциями). Задаются полином и двухместный предикат , определенный на словах в алфавите . Предикат должен обладать тем свойством, что для слов таких, что , значение вычисляется за время, ограниченное некоторым полиномом от . Соответствующая задача из класса NP состоит в том, чтобы выяснить, верно ли, что

для данного . (Для большинства задач класса NP выполняется , т.е. просто слово не длиннее слова .)

Пусть, например, , и непустые слова рассматриваются как двоичные неотрицательные целые числа. Тогда, очевидно, задачу проверки, является ли данное число составным, можно сформулировать как задачу класса NP: здесь предикат (условие) — это

“ и делится на ”,

. Проверка делимости на выполняется за время , где — битовая длина числа , т.е. длина числа как слова в алфавите .

Введем в рассмотрение класс задач P. Каждая задача этого класса состоит в проверке, обладает ли входное слово некоторым фиксированным свойством, и при этом свойство задано таким предикатом , что значение вычисляется полиномиальным алгоритмом. Легко устанавливается, что PNP: мы можем, например, взять , .

Обсуждавшаяся задача о составных числах принадлежит, как мы показали, NP. Благодаря существованию полиномиального алгоритма проверки простоты числа (см. п. 9) она принадлежит также P. Но для некоторых задач из NP до сих пор неизвестно, принадлежат ли они P. Выражение задает некоторый одноместный предикат . Вопрос, на который ответ ясен не всегда, состоит в том, найдется ли полиномиальный алгоритм вычисления значения предиката .

Одним из примеров задачи, для которой без труда устанавливается ее принадлежность NP, но не ясно, принадлежит ли она также и P, дает так называемая задача о выполнимости: определить для данной булевой формулы, записанной в конъюнктивной нормальной форме (КНФ) и содержащей переменные , принимает ли она значение “истина” при каких-либо булевых значениях этих переменных.

Если бы было доказано, что P=NP, то в широком спектре случаев мы бы легко устанавливали принадлежность задачи классу P (мы устанавливали бы существование полиномиального алгоритма; разработка такого алгоритма — это отдельный вопрос), так как принадлежность задачи классу NP нередко устанавливается достаточно легко. Неформально говоря, совпадение P и NP означало бы следующее: если для любого слова , соразмерного по длине с заданным словом , мы умеем быстро проверять, удовлетворяет ли вместе с каким-то фиксированным условиям, то мы сумеем и быстро проверить, существует ли хотя бы одно слово соответствующей длины, которое удовлетворяет вместе с этим условиям.

Если бы было доказано, что P=NP, то в широком спектре случаев мы бы легко устанавливали принадлежность задачи классу P (т.е. устанавливали бы существование полиномиального алгоритма проверки существования; разработка такого алгоритма — это отдельный вопрос): М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. М. Н. Вялый. Сложность вычислительных задач. Математическое просвещение, вып 4. M.: МЦНМО, 2000.

Неформально говоря, совпадение P и NP означало бы следующее: если для любого слова , соразмерного по длине с заданным словом , мы умеем быстро проверять, удовлетворяет ли вместе с каким-то фиксированным условиям, то мы сумеем и быстро проверить, существует ли хотя бы одно слово соответствующей длины, удовлетворяющее вместе с этим условиям.

Но равенство P=NP по сей день не доказано, и специалисты склоняются к предположению, что оно неверно (гипотеза PNP).

Разумеется, есть простой алгоритм проверки того, выполняется ли () для данного — можно перебирать все слова такие, что , проверяя каждый раз выполнение условия . Но при сложность этого алгоритма растет экспоненциально.

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

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

то говорят, что задача линейно сводится к задаче . В этом случае также говорят, что задача не сложнее задачи . Слово “линейно” в этом определении означает лишь то, что сложность получаемого алгоритма не является, скажем, квадратом, кубом и т.д. сложности алгоритма .

Пусть и — две вычислительные задачи. Если любому алгоритму решения задачи можно сопоставить такой алгоритм решения задачи , что то говорят, что задача линейно сводится к задаче . В этом случае также говорят, что задача не сложнее задачи . Слово “линейно” в этом определении означает лишь то, что сложность получаемого алгоритма не является, скажем, квадратом, кубом и т.д. сложности алгоритма .

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

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

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

Само существование NP-полных задач было доказано независимо С.А. Куком и Л.А. Левиным. К этим задачам относится, например, упоминавшаяся в п.9 задача о выполнимости булевой формулы. Установлением полиномиальной сводимости доказывается NP-полнота и многих других задач, среди которых задача проверки существования гамильтонова цикла в графе и др.

Само существование NP-полных задач было доказано независимо С.А. Куком и Л.А. Левиным: С. А. Кук. Сложность процедур вывода теорем. Кибернетический сборник, 1975, нов. серия, вып. 12, с. 5–15. Л. А. Левин. Универсальные задачи перебора. Проблемы передачи информации, 1973, т. 9, No 3, с. 115–116. См. также М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

К этим задачам относится, например, упоминавшаяся в п.9 задача о выполнимости булевой формулы.

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

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

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

Часто тривиальные верхние и нижние оценки выводятся легко, но получение оценок, в полной мере отражающих возможности алгоритма, требует немалых усилий и изобретательности. Впечатляющий пример дается алгоритмом Евклида. Пусть — натуральные числа, . Поиск наибольшего общего делителя (нод) чисел по алгоритму Евклида требует выполнения серии однотипных шагов, каждый из которых — деление с остатком:

В этом случае нод. Последовательность получаемых остатков убывает (остаток меньше делителя), при этом все остатки — неотрицательные целые. Поэтому число делений с остатком не превосходит . Но эта давшаяся легко верхняя оценка сложности по числу делений с остатком не отражает основных достоинств алгоритма Евклида. Оказывается, что число делений с остатком допускает по логарифмическое ограничение. Можно показать, что при использовании в качестве размера входа сложность алгоритма Евклида по числу делений в худшем случае есть . Второй сюрприз, который преподносит этот алгоритм, связан с его битовой сложностью. Примем теперь за размер входа битовую длину (количество цифр в двоичной записи) числа . В силу уже сказанного число делений с остатком есть в худшем случае. Битовая сложность наивного деления с остатком одного целого числа на другое, при условии, что битовая длина большего числа есть , является величиной порядка . Отсюда легко получается оценка для битовой сложности алгоритма Евклида. Но более тщательный анализ показывает, что битовая сложность алгоритма Евклида есть . Дополнительно можно показать, что привлечение более “быстрых” видов деления не позволяет существенно снизить эту сложность: для нее остается справедливой оценка при любом алгоритме деления, имеющем сложность .