* * *
В одном из простых определений сложными называются задачи, решение которых требует выполнения сопоставимого числа операций, а простыми считаются те, которые разрешимы не только с теоретической, но и с практической точки зрения, то есть в разумное время. Эти задачи часто обозначаются буквой Р (по первой букве английского слова «полином»), так как число операций для их решения примерно равно некоторому многочлену от времени выполнения.
Ученые заметили, что существуют задачи, найти решение которых очень сложно, а подтвердить его правильность относительно просто. Вернемся к примеру с отелем из главы 2, который на этот раз содержит конечное число комнат. Предположим, что группа из четырехсот человек хочет остановиться в отеле в те дни, когда там будет свободно всего сто номеров. Выбрать сто человек из четырехсот, не следуя какому-либо критерию, очень просто, однако заявка от группы сопровождалась одной странной просьбой: некоторые путешественники настолько не ладили друг с другом, что их нельзя было размещать в соседних номерах. Не стоит и думать, что эту задачу можно решить перебором всех возможных выборок ста человек из четырехсот, но при этом для любого предложенного решения достаточно будет подтвердить, что никакие два путешественника, которые не ладят друг с другом, не будут поселены в соседние номера. С этой задачей сможет справиться администратор отеля даже без помощи компьютера всего за несколько часов. Такие задачи, которые сложно решить, но легко проверить, математики относят к классу NP.
Пока что мы говорили о сложности задач как о неотъемлемой части их формулировки. Эта точка зрения априори ошибочна, так как сложной или простой является не задача сама по себе, а наш способ ее решения. Возможно, найденное нами решение требует выполнения множества операций, но при этом существует другое, более простое. В этом случае наше решение относится к классу NP, в то время как сама задача — к классу Р. Решение задачи о коммивояжере заключалось в переборе всех возможных маршрутов. Однако в таблице показано, что при смене порядка обхода городов на противоположный длина маршрута не меняется. Следовательно, выбор маршрута Париж — Лондон — Берлин — Рим — Париж ничем не отличается от маршрута Париж — Рим — Берлин — Лондон — Париж, поэтому достаточно рассмотреть половину исходных случаев. На практике подобное упрощение не слишком полезно, так как половина огромного числа по-прежнему остается огромным числом. Этот аспект имеет скорее философский характер: если в первом решении мы упустили из вида столь тривиальную деталь, то сколько подобных моментов мы еще не учли? Мы сказали, что наша исходная точка зрения априори ошибочна, поскольку неизвестно, существуют ли задачи, для которых сложность является неотъемлемым свойством их формулировки, а не решений. К числу таких задач, возможно, относится задача о коммивояжере, пока что никому не удалось доказать, что все ее решения являются сложными.
* * *
Р И NP
Как вы увидели в главе 3, датой символического начала математики XX века считается август 1900 года, когда Гильберт обнародовал свой список из двадцати трех задач на конференции в Париже. Вновь в Париже, но уже сто лет спустя, экспертная комиссия из Института Клэя выбрала семь открытых задач, которые, по ее мнению, обозначили направление математических исследований нового столетия. Четвертая проблема в этом списке, известная как проблема равенства классов Р и NP, заключается как раз в том, чтобы подтвердить, существуют ли задачи класса NP сами по себе или же, напротив, любую задачу, решение которой можно проверить за полиномиальное время, также можно быстро решить, найдя некий хитроумный алгоритм. Того, кто найдет решение этой проблемы, ждет премия в один миллион долларов. Как видите, математика иногда может приносить доход.
* * *
В связи с этим определением сложности возникает еще одно замечание: в подобной трактовке не проводится различие между задачами, для решения которых требуется одинаковое число операций. По нашему определению, запомнить пароль из двенадцати символов — это простая или сложная задача независимо от того, из каких символов состоит пароль, так как для этого неизменно потребуется двенадцать действий: запомнить первый символ, второй, третий и т. д. до двенадцатого.