‍Теория сложности

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

Пре­жде всего надо дого­во­риться о классе изу­ча­емых объек­тов, т. е. соб­ственно алго­ритмов. Еди­ного мне­ния на этот счёт нет. Само слово «алго­ритм» про­ис­хо­дит от имени вели­кого пер­сид­ского учё­ного аль‐­Хо­резми, в 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=p_1^{d_1p_2^{d_2}\>…\> p_k^{d_k}}$ и $b=p_1^{e_1p_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‐пол­ной задачи, чего матема­тики делать пока не умеют. О попу­ляр­но­сти этой задачи сви­де­тельствует, в част­но­сти внима­ние, про­яв­ля­емое к ней люби­те­лями от матема­тики — по этому кри­те­рию про­блема пере­бора, возможно, уже пре­взошла гипо­тезу Ферма. Однако и про­фес­си­о­налы за пре­де­лами матема­ти­че­ской логики и компью­тер­ных наук, без­условно, отдают ей долж­ное. Про­блема пере­бора — одна из семи задач, за реше­ние кото­рой матема­ти­че­ский инсти­тут Клэя учре­дил пре­стиж­ную премию. Как известно, пока решена только одна из них (гипо­теза Пуан­каре — Г. Перельман); для реше­ния оставшихся, ско­рее всего, также пона­до­бятся новые идеи и под­ходы, о при­роде кото­рых мы в слу­чае про­блемы пере­бора не имеем даже при­бли­зи­тель­ного пред­став­ле­ния.