Cтр. 118

Теория сложности
Поделиться…

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

Прежде всего надо договориться о классе изучаемых объектов, т. е. собственно алгоритмов. Единого мнения на этот счёт нет. Само слово «алгоритм» происходит от имени великого персидского учёного аль–Хорезми, в IX веке описавшего правила обращения с позиционной системой счисления (любопытно, что слово «алгебра» происходит из того же сочинения). После этого в течение долгого времени под алгоритмами понималось искусство и правила счёта; алгоритмы, оперирующие с целыми или рациональными числами мы будем называть числовыми. Следующей ступенью общности являются алгоритмы, работающие с произвольными дискретными данными: графами, массивами, текстами, расписаниями и т. д. Это алгоритмы в строго математическом смысле этого слова. Они были определены и впервые изучены в работах великих математических логиков прошлого столетия, таких, как К. Гёдель, А. А. Марков, П. С. Новиков, А. Тьюринг, А. Чёрч, создавших строгую теорию вычислимости, и это именно тот класс алгоритмов, который используется в современных устройствах. Наконец, алгоритмы можно понимать и в наиболее широком смысле, как набор конкретных и полностью определённых правил, выполнение которых позволит добиться поставленной цели за конечное время.

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

Мы попытаемся проиллюстрировать её основные идеи на простом модельном примере. Рассмотрим задачу нахождения наибольшего общего делителя $\mbox{НОД}(a,b)$ натуральных чисел $a$ и $b$ ($a<b$), т. е. наибольшего возможного $d$ такого, что как $a$, так и $b$ делится на $d$. Эта школьная задача и её обобщения (скажем, на случай многочленов) возникают везде, где применяется теория чисел, в первую очередь — в криптографии. Как её решать? Возможны несколько подходов.

Первый алгоритм (совсем примитивный). Перебираем все числа от $a$ до 1 в порядке убывания (т. е. начиная с $a$), пока не натолкнёмся на нужное.

Второй алгоритм (после некоторого раздумья). Давайте лучше последовательно делить $a$ на 2, 3, 4, и пробовать $a/2$, $a/3$, $a/4$ (имеется в виду, что если $a/k$ не является целым, мы его пропускаем, а если оно целое, пробуем поделить на него $b$) и т. д., пока не доберёмся примерно до $\sqrt a$. Если нам повезло (а это заведомо случится при $\mbox{НОД}(a,b)\geq\sqrt a$), то хорошо, а если нет, то переходим к первому способу, но на этот раз начиная с $\sqrt a$, а не с $a$.

Третий алгоритм (для математически продвинутых). Разложим
$a$ и $b$ на простые множители: $a=\smash{p_1^{d_1}p_2^{d_2}\>…\> p_k^{d_k}}$ и $b=\smash{p_1^{e_1}p_2^{e_2}\>…\> p_k^{e_k}}$ (некоторые степени здесь могут быть нулевыми). Тогда наибольший общий делитель вычисляется по нехитрой формуле
$$
d= p_1^{\min(d_1,\>e_1)}\>p_2^{\min(d_2,\>e_2)}\>…\> p_k^{\min(d_k,\>e_k)}.
$$

Для того, чтобы разумным способом сравнивать различные подходы, очевидно, нужна некоторая общая «линейка» (или «мера»). Можно пытаться использовать в качестве меры просто число сделанных попыток, тогда сразу видно, что в наихудшем случае первому алгоритму понадобится порядка $a$ попыток, в то время как второму — порядка $2\sqrt a$, что уже является ощутимым прогрессом. Но как их сравнивать с третьим алгоритмом, использующим совсем другие (и более продвинутые) идеи?

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

По этой причине универсальная мера может быть введена лишь на следующей ступени общности в рамках классической теории вычислимости, и по–научному она называется числом тактов работымашины Тьюринга — абстрактного вычислительного устройства, предложенного великим британским математиком А. Тьюрингом в 1936 году. На интуитивном уровне это число элементарных (т. е. далее неразложимых) шагов, которые требуется предпринять для достижения поставленной цели. В случае классической машины Тьюринга это операции совсем примитивные: сдвинуться по вычислительной ленте на одну позицию влево или вправо, прочесть или перезаписать обозреваемый символ и т. д. Но читатель, немного знакомый с программированием, может без особого ущерба для понимания предполагать, что мы подсчитываем число выполнений инструкций, содержащихся в программе, за всё время её работы. Именно число выполнений, а не число самих инструкций — последнее приводит к так называемой колмогоровской сложности, которую мы здесь не рассматриваем.

Поговорим теперь немного о роли случая. Если мы станем применять наши алгоритмы к $a=54 284 452$, $b=67 855 565$, то скажется это на их работе по–разному. Первый и третий специфики $a$ и $b$ просто не заметят, и будут работать со своей обычной производительностью, а второй алгоритм выдаст правильный ответ $\mbox{НОД}(a,b)=13 571 113$ с третьей попытки. Означает ли это, что он однозначно лучше?

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

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

Чтобы разобраться, в чём же этот подход состоит, заметим, что наиболее важная и универсальная информация о числе — это количество знаков в его записи ($n$). Скажем, в нашем примере $n=8$, если запись десятичная и $n≈ 25$, если она двоичная — отличие чуть больше, чем в три раза. Конечная цель разработчиков алгоритмов — построить алгоритм, который гарантированно решает задачу за $f(n)$ элементарных шагов, независимо от того, какие именно $n$–разрядные числа ему даны (где $f$ — некоторая функция, желательно медленно растущая). Подчеркнём, что $n$ — именно число знаков в записи числа, а не само это число; чтобы почувствовать разницу, достаточно заметить, что число, выражающее число атомов в видимой части Вселенной вполне умещается на одной строчке, хотя и убористым почерком.

Разберём ещё раз с этой точки зрения алгоритмы для нашего модельного примера. Первому алгоритму в худшем случае понадобится порядка $f(n)≈ 10^n$ элементарных операций. Это произведение числа попыток на число операций, необходимых для каждой из них, но поскольку для этого требуются лишь простые арифметические действия (впрочем, как вытекает из статьи «Быстрая арифметика», даже для них ситуация не настолько проста, насколько кажется), второй множитель оказывается небольшим полиномом от $n$, и по сравнению с экспоненциальными функциями им вполне можно пренебречь. Знак приближённого равенства $≈$ вызван именно этим обстоятельством. Второй алгоритм в наихудшем случае (хорошее упражнение — попытаться понять, в каком) потребует $f(n)≈ 10^{n/2}$ операций, так что он в самом деле слегка лучше первого. Намного поучительнее ситуация с третьим алгоритмом. Понятно, что его успех в первую очередь зависит от следующего вопроса: насколько быстро мы умеем раскладывать числа на простые множители?

Этот вопрос занимал математиков с античных времён, за тысячелетия до того, как предположение о том, что эффективного способа решения задачи о разложении на простые множители не существует, легло в основу большинства используемых в современном мире криптосистем. Глубоко вдаваться в этот вопрос у нас, к сожалению, возможности нет (данная тема заслуживает отдельной статьи), поэтому отметим лишь, что наилучший из известных сегодня алгоритмов в наихудшем случае работает за время $f(n)=10^{C n^{1/3}(\log_2 n)^{2/3}}$, где $C>0$ — не слишком большая константа. Это уже существенно лучше в сравнении с $f(n)$ для первого и второго алгоритмов, но функция всё равно растёт экспоненциально быстро.

Давайте ещё немного поразмышляем над третьим алгоритмом. По своему виду он является сведением одной задачи к другой, а именно, задачи нахождения наибольшего общего делителя к задаче разложения чисел на простые множители. Это означает, что любой прогресс в решении второй задачи автоматически влечёт равнозначный прогресс в решении первой. Как мы увидим ниже, общее понятие сводимости одной задачи к другой играет исключительно важную роль в теории сложности алгоритмов. В программистских терминах оно соответствует понятию процедуры или подпрограммы; надо, правда, ещё позаботиться о том, чтобы процедура вызывалась «не слишком часто» (в случае третьего алгоритма — два раза) и для «не слишком» больших значений параметров (в нашем случае это просто исходные данные $a$ и $b$). В том, что касается нахождения наибольшего общего делителя, пора переходить к развязке, многими читателями, по–видимому, давно ожидаемой. «Начала» великого древнегреческого математика Евклида (около 300 года до н. э.) по праву считаются одной из величайших книг в истории человечества, в которой были заложены основы современной геометрии (термины «евклидово пространство», «евклидова метрика» и др. восходят к тексту «Начал»), и во многом всей современной математики вообще. Гораздо менее известно, что книга VII содержит описание старейшего из дошедших до нас алгоритмов, который к тому же активно используется и сегодня.

Алгоритм четвёртый и последний (алгоритм Евклида). Разделим $b$ на $a$ с остатком: $b=h\cdot a+r$, где $0\leq r\leq a-1$. После этого рекурсивно применяем алгоритм к паре $(r,a)$: делим $a$ на $r$, $a=u\cdot r+s$ и заменяем пару $(r,a)$ на $(s,r)$. Продолжаем действовать, пока не доберёмся до пары вида $(0,d)$. Второе число в полученной паре и будет искомым ответом.

Почему этот алгоритм работает правильно? И, даже если так, почему он работает быстро? Ответами на вопросы такого рода (когда они не вполне очевидны, конечно) занимается специальный раздел теории сложности, называемый анализом алгоритмов. Алгоритм Евклида работает правильно, потому что $\mbox{НОД}(a,b) = \mbox{НОД}(r,a) =\mbox{НОД}(s,r) =…$ Тем самым, наибольший общий делитель является, как любят говорить математики, инвариантом данной процедуры (сравните со статьёй «Игра в „15“»), а для заключительной пары $(0,d)$ он как раз и равен $d$. Быстро он работает потому, что всегда имеет место соотношение $(a+r)\leq\frac 23(a+b)$. Поэтому сумма чисел в паре убывает экспоненциально и, в частности, алгоритм заведомо сойдётся за $f(n)≈ 10n$ итераций, что является линейной функцией от числа знаков $n$ в записи $a$ и $b$. Результат оказывается настолько впечатляющим по сравнению с нашими предыдущими подходами, что их можно было бы смело отнести к разряду исторических курьёзов, если бы не то обстоятельство, что алгоритму Евклида уже порядка 2500 лет… Учитывая его простоту и эффективность, алгоритм Евклида и его обобщения широко используются в наши дни, как в теоретической математике, так и в приложениях, преимущественно в криптографии.

Фундаментальным отличием функции $10n$ от всех встречавшихся нам ранее является тот факт, что она полиномиальная (т. е. имеет вид $C\cdot n^d$ для некоторых $C$, $d>0$), а не экспоненциальная. В современной теории сложности алгоритмы с такой оценкой сложности (в наихудшем случае) называются полиномиальными, а класс всех задач, которые допускают хотя бы один полиномиальный алгоритм, имеет преднамеренно лаконичное название «P». В этих терминах алгоритм Евклида устанавливает, что задача нахождения наибольшего общего делителя двух чисел лежит в классе P.

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

Класс P также крайне удобен с математической точки зрения, и это вытекает из того нехитрого замечания, что при перемножении двух полиномов или подстановке одного полинома в другой всё равно получится полином. Скажем, при анализе наших предыдущих алгоритмов мы писали «$f(n)≈$» чтобы различать число «попыток» (или итераций) и число «элементарных операций». Однако все арифметические действия заведомо выполнимы за полиномиальное время (смотри «Быстрая арифметика»), поэтому при исследовании принадлежности классу P этой разницей можно пренебречь и сосредоточиться на том, что на самом деле важно, т. е. на числе итераций. Такие ситуации встречаются сплошь и рядом.

Ещё одним выражением этой замечательной инвариантности является то обстоятельство, что класс P не зависит от выбора вычислительной модели. У использующих C++ и Basic (и даже предпочитающих FORTRAN или, совсем по классике, машины Тьюринга) класс P один на всех. Предположение о том, что так будет всегда, для любого разумного вычислительного устройства, известно, как расширенный тезис Тьюринга—Чёрча.

Полиномиальные алгоритмы (во многих случаях весьма нетривиальные) существуют для многих естественных задач. Элементарные арифметические операции в этой связи уже упоминались ранее; с их более тонкой градацией внутри класса P можно познакомиться в статье «Быстрая арифметика». Алгоритм Евклида даёт полиномиальный алгоритм для нахождения наибольшего общего делителя двух чисел (кстати, как насчёт наименьшего общего кратного?). «Исключительно плохие» примеры для симплекс–метода означает: примеры, на которых он работает экспоненциальное время. Первый по–настоящему полиномиальный алгоритм для линейного программирования был впервые построен советским математиком Л. Хачияном в 1979 году.

Перелистаем настоящий сборник.

Многие важные задачи для транспортных потоков [«Математика транспортных потоков»] допускают полиномиальные алгоритмы.

Алгоритмы, связанные с Интернетом [«Математика интернета»] являются алгоритмами лишь в широком смысле, так как сами задачи по своей сути динамические и распределённые. О них мы поговорим немного позже, пока лишь отметим, что полиномиальность здесь является требованием заведомо необходимым, но никак не достаточным. Имеющие дело с «большими данными» (big data) обычно настаивают на линейных алгоритмах, т. е. таких, для которых $f(n)\leq Cn$.

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

Алгоритмы, используемые для сжатия информации, также являются полиномиальными. Борьба идёт за улучшение скорости кодирования и декодирования внутри класса P — как и в случае «больших данных», разница между линейными и, скажем, квадратичными алгоритмами оказывается весьма ощутимой.

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

«Игру в „15“» можно легко обобщить до «игры в „$n^2{-}1$“» для произвольного натурального $n$. Существует (скорее всего — строго это утверждение автор не проверял!) полиномиальный относительно $n$ алгоритм, позволяющий для двух чётных позиций указать путь, переводящий одну в другую. Кстати, эта задача легко сводится (в нашем смысле) к своему частному случаю, когда одна из позиций является полностью упорядоченной; может ли читатель понять, как именно?

Ещё одна задача, которая занимала математиков на протяжении тысячелетий — это задача определения простоты числа. Хотя «почти полиномиальные» алгоритмы (скажем, вероятностные алгоритмы, которым разрешается подбрасывать монетку и ошибиться в ответе с малой вероятностью) были известны довольно давно, полиномиальный алгоритм в строгом смысле этого слова был построен лишь в 2002 году. Это открытие вызвало огромный резонанс как среди математического сообщества, так и за его пределами.

По–видимому, у ряда читателей в этот момент должно возникнуть лёгкое недоумение: а в чём собственно разница между тестированием простоты и разложением на простые множители? Не одно ли это и то же?

Оказывается, что нет, и в этом проявляется существенное и довольно тонкое различие между конструктивными доказательствами и чистыми доказательствами существования. Скажем, многие из «почти полиномиальных» алгоритмов (с окончательным алгоритмом тестирования простоты ситуация чуть сложнее, но принцип тот же) в качестве доказательства того, что число $m$ составное, выдадут контрпример к малой теореме Ферма, т. е. такое $a$, что $a^{m-1}\neq 1$ в арифметике по модулю $m$. Можно ли из этого доказательства извлечь фактическое разложение $m$ на простые множители? Ответ на этот вопрос неизвестен, положительный ответ в виде полиномиального алгоритма привёл бы к весьма ощутимым изменениям в современной цивилизации, во многом основанной на вере в то, что криптографические системы типа RSA являются устойчивыми.

Давайте и мы попробуем наши скромные силы в задаче о разложении на простые множители. Как мы уже отмечали (третий алгоритм), задача нахождения НОД двух чисел сводится к задаче факторизации (разложения на простые множители), а алгоритм Евклида делает это сведение ненужным с практической точки зрения. Математика, однако, развивается по своим собственным законам, и тот факт, что какие-то подходы или результаты оказываются «устаревшими» (учитывая почтенный возраст алгоритма Евклида, данное слово здесь, конечно, весьма условно) совершенно не означает, что заложенные в них идеи также оказываются бесполезными. В данном случае естественно попытаться поступить наоборот и использовать алгоритм Евклида для того, чтобы раскладывать числа на множители. Ведь для того, чтобы отыскать нетривиальный делитель составного числа $m$ (кстати, понятно ли, почему задача полной факторизации сводится к этой?), достаточно «всего лишь» разыскать такое $n$, для которого $1<\mbox{НОД}(m,n)<m$, после чего можно воспользоваться (эффективным!) алгоритмом Евклида.

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

1) некоторых важных «криптоаналитических» алгоритмов (т. е. алгоритмов, ищущих уязвимые места в криптографических системах с открытым ключом);

2) полиномиального квантового алгоритма для факторизации чисел, придуманного американским математиком П. Шором в 1995 году.

На последнем результате стоит остановиться подробнее, так как он дал мощный толчок к развитию огромной современной области, называемой квантовыми вычислениями, в которой бок о бок трудятся математики, специалисты в области теоретической информатики и физики. Никакого подвоха здесь нет: компьютер, который в состоянии использовать законы квантовой механики, в самом деле может разлагать $n$–разрядные числа на простые множители за время, чуть большее $Cn^2$. Кстати, сам алгоритм использует весьма красивую и неожиданную математику: применение в самом конце алгоритма Евклида оказывается лишь верхушкой айсберга.

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

1) построение практичного квантового компьютера невозможно (и, тем самым, эта модель приравнивается к «неразумным»);

2) расширенный тезис Тьюринга—Чёрча неверен (и, видимо, возможны отклонения от него, использующие и другие физические или биологические законы);

3) для факторизации чисел существует классический полиномиальный алгоритм (со всеми вытекающими отсюда последствиями).

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

Теперь мы немного поговорим о проблеме нижних оценок в теории сложности вычислений, а именно, доказательстве того, что для конкретных интересных задач любой алгоритм должен иметь сложность $f(n)\geq \varepsilon\cdot b(n)$, где $b(n)$ — некоторая фиксированная функция. Вершиной здесь было бы доказательство того, что какая–нибудь интересная задача не принадлежит классу P, т. е. не допускает никакого алгоритма с верхней оценкой сложности $f(n)\leq Cn^k$ (о перспективных кандидатах мы поговорим позже). Возьмём для примера задачу факторизации. Красной нитью через наше изложение проходил тезис о том, что задача факторизации чисел не лежит в P, причём, в отличие от тезиса Тьюринга—Чёрча, это математическое предположение. Количество человеко–часов, потраченное на его опровержение (в том числе и часов, относящихся к наиболее сильным специалистам по теории чисел и алгоритмам) не поддаётся никакому исчислению. Означает ли это, что нам следует просто принять его за некий физический закон и заняться чем–то ещё?

Конечно же, для любого работающего математика этот вопрос чисто риторический и может в лучшем случае вызвать лёгкую улыбку. Тот факт, что на протяжении весьма долгого времени никто не был в состоянии предъявить нетривиальное решение уравнения $x^n+y^n=z^n$ или трёхмерное многообразие с «дикими» свойствами (контрпример к гипотезе Пуанкаре), математиков в поиске доказательства соответствующих утверждений только раззадоривал, и совсем не напрасно. В процессе их решения с кульминацией, наступившей в работах Э. Уайлса и Г. Перельмана, соответственно, были созданы целые стройные теории, занявшие своё достойное место в здании современной математики.

Точно так же обстоит дело и с проблемой нижних оценок сложности, с той разницей, что она в настоящий момент остаётся широко открытой, хотя ряд обнадёживающих результатов и был получен в 80–е и 90–е годы XX века. По–видимому, для её полного решения потребуются некоторые, пока неизвестные идеи (впрочем, по сравнению, скажем, с теоремой Ферма или гипотезой Пуанкаре, проблема нижних оценок сложности находится в младенческом возрасте). Причину такого положения дел понять легко. Любое доказательство несуществования эффективного (скажем, полиномиального) алгоритма для данной задачи должно непременно учитывать не только все уже существующие идеи для построения такого алгоритма, но также и все потенциальные идеи, которые могут появиться в будущем: в этом, собственно, и состоит смысл теории сложности. Этот класс идей весьма широк, и большинство известных частных результатов по проблеме нижних оценок получаются как раз путём его сужения.

В заключение нашего краткого очерка следует рассказать про NP–полноту: это именно тот раздел, в котором успехи теории сложности вычислений уже оказываются весьма впечатляющими. Основы теории NP–полноты были заложены в работах американских математиков C. Кука, Р. Карпа и советского математика Л. Левина в начале 70–х годов.

Давайте ещё раз взглянем на задачу нахождения нетривиального делителя составного числа и сравним её с двумя другими задачами из данного сборника: нахождения гамильтонова цикла [«От прогулок по Кёнигсбергу до реконструкции генома»] и решения судоку [«Разгадывание судоку»]; последнюю, конечно, надо обобщить на случай таблицы $n^2\times n^2$. Что между ними всеми общего?

На «философском» уровне понятно, что решение всех таких задач разбивается на два совершенно неравноценных этапа: поиск или угадывание правильного ответа и его проверка. Последнюю во всех случаях провести легко и можно поручить компьютеру или даже школьнику. Насчёт того, как правильный ответ найти, никаких общих рецептов у нас нет, а в лучшем случае есть лишь разумные советы, иногда называемые эвристиками (смотри, например, «Разгадывание судоку»). Хорошо, однако, то, что правильный ответ по крайней мере оказывается коротким или, более математически, его битовая длина $m$ не превосходит полинома от битовой длины записи $n$ самой задачи. Поэтому всегда имеется тривиальный переборный алгоритм, который вместо организованного поиска просто перебирает подряд все возможности, пока не натолкнётся на нужную. Его сложность в наихудшем случае порядка $2^m\sim 2^{Cn^k}$. Учитывая скорость роста экспоненциальной функции, это, конечно, не ахти, но стоит отметить, что бывают ситуации и намного хуже.

Из данного в предыдущем абзаце описания сравнительно легко сконструировать математическое определение: класс задач, в которых проверка ответа полиномиальна, т. е. лежит в классе P. Эквивалентное определение получается, если в приведённое в начале заметки описание машины Тьюринга добавить пункт о её недетерминированности, т. е. разрешить машине по своему усмотрению выбирать один вариант поведения из списка предложенных. Полученный таким образом класс задач называется NP, где «N» напоминает о недетерминированности. Большинство задач, которые мы обсуждали ранее, принадлежат этому классу или могут быть легко приведены к требуемому виду. Такая широкая распространённость, конечно же, не случайна. Она отражает тот факт, что NP является неплохой математической моделью любой организованной творческой деятельности, состоящей из собственно творческого акта поиска решения и (как правило быстрой и рутинной) фазы его проверки. Учитывая такое многообразие задач в NP, a priori следовало бы ожидать существование внутри этого класса богатой иерархической структуры, пытающейся сортировать задачи в соответствии с их внутренней сложностью, предположений о том, куда именно та или иная задача попадает и т. д.

Оказывается, что ничего этого не происходит. За весьма немногими исключениями, класс NP фактически распадается ровно на два больших куска. Первый кусок — это уже известный нам класс P, состоящий из всех алгоритмических задач, допускающих хотя бы один эффективный (полиномиальный) алгоритм. Иными словами, это те задачи, в которых перебор вариантов удаётся заменить эффективной процедурой, что мы, собственно, и наблюдали на примере алгоритма Евклида (другой хрестоматийный пример — задача про эйлеров цикл из статьи «От прогулок по Кёнигсбергу до реконструкции генома»).

На противоположном полюсе находятся так называемые NP–полные задачи, обладающие тем свойством, что к ним полиномиально сводится любая другая задача из класса NP. Оказывается, что и задача разгадывания судоку и задача нахождения гамильтонова цикла из статьи «От прогулок по Кёнигсбергу до реконструкции генома» и ещё более тысячи (с учётом всех вариаций — порядка $10 000$) алгоритмических задач из самых разных областей математики, компьютерных наук, естествознания, биологии, социологии и т. д. NP–полны. Таким образом, любой эффективный алгоритм для разгадывания судоку может быть перестроен в эффективный алгоритм для разложения чисел на простые множители, построения гамильтонова цикла и массы других полезных вещей. Все такие редукции имеют ярко выраженный «модулярный характер»: полиномиальное сведение, скажем, гамильтонова цикла к судоку разбивается на несколько сравнительно коротких переходов от одной естественной промежуточной задачи к другой. Все встречающиеся нам по дороге задачи могут также быть зачислены в NP–полные.

А вот между этими двумя полюсами нет практически ничего. Одна NP–задача, которую мы не умеем классифицировать — это разложение чисел на простые множители; имеется ещё несколько примеров такого типа, мотивированных криптографическими предположениями. Все они обладают тем свойством, что правильный ответ единственен. Примером, в котором последнее свойство не выполняется, служит задача изоморфизма графов (нарисованы два графа, можно ли их так «наложить» друг на друга, что они совпадут) и её разновидности. Вот, пожалуй, и все (или, по крайней мере, наиболее важные) естественные задачи, статус которых пока неизвестен. Так что с уверенностью можно сказать, что классификация переборных задач на простые (P) и максимально трудные (NP–полные) — это один из наиболее успешных классификационных проектов в истории науки.

По всем этим причинам задача о совпадении классов P и NP (известная также, как проблема перебора) — это одна из центральных открытых проблем современной математики. Большинство специалистов верят в то, что $\mbox{P}\neq \mbox{NP}$. Но доказательство этого факта сводится к проблеме нижних оценок для произвольно выбранной NP–полной задачи, чего математики делать пока не умеют. О популярности этой задачи свидетельствует, в частности внимание, проявляемое к ней любителями от математики — по этому критерию проблема перебора, возможно, уже превзошла гипотезу Ферма. Однако и профессионалы за пределами математической логики и компьютерных наук, безусловно, отдают ей должное. Проблема перебора — одна из семи задач, за решение которой математический институт Клэя учредил престижную премию. Как известно, пока решена только одна из них (гипотеза Пуанкаре — Г. Перельман); для решения оставшихся, скорее всего, также понадобятся новые идеи и подходы, о природе которых мы в случае проблемы перебора не имеем даже приблизительного представления.