Работа Перельмана, несомненно, чрезвычайно важна в области чистой математики, но применить доказательство гипотезы Пуанкаре на практике шансов немного. То же самое относится и к большинству других «Проблем тысячелетия», которые на момент написания этой книги оставались нерешенными. Однако доказательство или опровержение гипотезы номер семь – известной в математическом сообществе под кратким и несколько загадочным названием P vs NP (а в российском математическом сообществе еще и как проблема перебора) – может иметь широкомасштабные практические последствия в таких разнообразных областях, как интернет-безопасность и биотехнология.

В основе проблемы P vs NP лежит идея, что проверить правильность решения задачи зачастую проще и быстрее, чем собственно решение найти. Этот важнейший из открытых математических вопросов сводится к следующему: если положительный ответ на какой-то вопрос можно довольно быстро проверить при помощи компьютера, верно ли, что ответ на этот вопрос можно довольно быстро найти?

Чтобы провести аналогию, представьте, что вы собираете пазл из однообразного изображения, вроде картинки чистого голубого неба. Перепробовать все возможные комбинации кусочков, чтобы понять, подходят ли они друг другу, – трудная задача; сказать, что она займет много времени – это преуменьшение. Однако, как только пазл закончен, правильность его сборки проверить легко. Более строгие определения эффективности математические выражаются в описании того, насколько быстро работает алгоритм по мере усложнения проблемы – когда к пазлу добавляется больше кусочков. Набор задач, которые можно решить быстро (в так называемом полиномиальном времени), называется классом сложности P. Бóльшая группа задач, которые можно быстро проверить, но не обязательно можно быстро решить, называется классом сложности NP (что расшифровывается как недетерминированное полиномиальное время). Задачи типа P – это подмножество задач типа NP, так как, решив задачу быстро, мы автоматически проверяем найденное решение.

А теперь представьте, что нужно построить алгоритм собирания любого пазла. Если алгоритм входит в группу P, то время, затраченное на его решение, может зависеть от количества элементов пазла, квадрата, куба или даже большей степени этого числа. Например, если алгоритм зависит от квадрата количества элементов, то для сбора пазла из двух элементов может потребоваться 4 (2²) секунды, для сбора пазла из 10 элементов – 100 (10²) секунд, а для пазла из 100 элементов – 10 000 (100²) секунд. Этот отрезок времени кажется достаточно долгим, но он укладывается в считаные часы. Однако если алгоритм входит в группу NP, то с увеличением количества кусочков время, затрачиваемое на его решение, может вырасти по экспоненте. Если на сбор пазла из 2 элементов понадобятся те же 4 (2²) секунды, то на пазл из 10 элементов – уже 1024 (2¹⁰) секунды, а на пазл из 100 элементов – 1 267 650 600 228 229 401 496 703 205 376 (2¹⁰⁰) секунд, что значительно превышает время, прошедшее с момента Большого взрыва. Оба алгоритма требуют больше времени на исполнение с усложнением задачи (ростом количества элементов), но алгоритмы для решения общих проблем группы NP с усложнением задачи быстро становятся непригодными для ее решения. В сущности, литерой «P» можно было бы обозначать проблемы, Решаемые на практике, а литерами «NP» – Не Решаемые на практике.

Проблема «P vs NP» заключается в вопросе, все ли проблемы класса NP, решения которых можно быстро проверить, но алгоритм быстрого решения, которых неизвестен, действительно являются и членами класса P. Может быть, проблемы класса NP имеют практический алгоритм решения, но мы его просто еще не нашли? В математической терминологии, равны ли P и NP? Если да, то, как мы увидим, потенциал применения этого равенства – даже для решения повседневных задач – огромен.

Роб Флеминг, главный герой классического романа 90-х Ника Хорнби «Hi-Fi», – одержимый музыкой владелец магазина подержанных пластинок Championship Vinyl. Периодически Роб пересортировывает свою огромную коллекцию пластинок в разном порядке – по алфавиту, по хронологии и даже автобиографически (порядок, в котором он покупал свои пластинки, рассказывал историю его жизни). Сортировкой и составлением каталогов занимаются не только любители музыки в поисках катарсиса – это способ организации информации, позволяющий быстро сгруппировать ее в соответствии с необходимыми критериями и получить данные по конкретному запросу. Когда вы одним кликом группируете письма в своем электронном почтовом ящике по дате, отправителю или теме, ваш клиент электронной почты реализует эффективный алгоритм сортировки. eBay реализует алгоритм сортировки, когда вы выбираете категории товаров, соответствующих вашему поисковому запросу, переходя от «наилучшего соответствия», к «наименьшей цене» или «заканчивающиеся быстрее всего». После того как Google определит, насколько точно веб-страницы соответствуют заданным вами поисковым критериям, ему необходимо быстро отсортировать страницы и представить их вам в правильном порядке. Эффективные алгоритмы, позволяющие достичь этой цели, пользуются большим спросом.

Один из способов сортировки набора предметов заключается в составлении списков, где зафиксированы все возможные комбинации предметов, и последующей проверке всех этих записей, чтобы убедиться, что порядок правильный. Представьте, что ваша музыкальная коллекция состоит всего из пяти альбомов – по одному от Led Zeppelin, Queen, Coldplay, Oasis и Abba. Но эти пять альбомов можно расставить (сгруппировать) 120 разными способами. Шесть альбомов – 720 способами, десять – более чем тремя миллионами способов. Количество комбинаций растет настолько быстро, что любой уважающий себя фанат пластинок запретит себе даже пытаться перепробовать их все: это просто нереально.

К счастью, как вы, вероятно, знаете из собственного опыта, сортировка коллекции записей, книг или DVD-дисков является проблемой категории Р – одной из тех, для которых есть практическое решение. Самый простой алгоритм такого решения называется пузырьковая сортировка (или сортировка простыми обменами). Работает он следующим образом. Мы сокращаем исполнителей из нашей скудной коллекции записей до первых букв – L, Q, C, O и A с тем, чтобы расставить их в алфавитном порядке. Алгоритм пузырьковой сортировки проверяет весь набор попарно слева направо и меняет соседние альбомы, если они расположены неверно (не в алфавитном порядке). Он продолжает просматривать альбомы, пока не расставит все в правильном порядке, рассортировав всю коллекцию. На первом проходе L остается на том же месте (в алфавите она идет раньше Q), но при сравнении Q и C алгоритм определит, что они расставлены неверно и поменяет их местами. Дальше сортировка продолжается: в процессе первого прохода местами поменяются Q и O, а затем – Q и A; список приобретет вид L, C, O, A, Q. К концу этого прохода Q окажется на своем законном месте в конце списка. На втором проходе С поменяется местами с L, а А – с О, в результате чего О тоже окажется в правильном месте: C, L, A, O, Q. Для того чтобы поставить А на первое место и выстроить весь список в правильном алфавитном порядке, потребуется еще два прохода.

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

В 2008 году во время предвыборной кампании в США Джона Маккейна, объявившего о намерении выставить свою кандидатуру, вскоре после этого пригласили выступить в Google, чтобы обсудить его политическую платформу. Эрик Шмидт, в тот момент генеральный директор Google, в шутку сказал тогда Маккейну, что баллотироваться на пост президента – примерно то же самое, что и проходить собеседование при приеме на работу в Google. А затем задал ему один из вопросов, которые задают на таком собеседовании: «Как вы определите хорошие способы сортировки одного миллиона 32-битных целых чисел в двух мегабайтах оперативной памяти?» Маккейн смешался, а Шмидт, повеселившись, быстро перешел к следующему вопросу – уже серьезному. Шесть месяцев спустя, когда в прицеле Google оказался Барак Обама, Шмидт задал ему тот же самый вопрос. Обама посмотрел на публику, потер бровь и начал: «Ну, э-э-э…». Чувствуя растерянность Обамы, Шмидт попытался вмешаться, но как раз в этот момент Обама закончил, глядя Шмидту прямо в глаза: «…нет-нет-нет, я думаю, что делать это через “пузырьки” – не лучшая идея», – под гром аплодисментов и одобрительные крики собравшихся компьютерщиков. Неожиданная эрудиция Обамы – шутка «для посвященных» о неэффективности пузырькового алгоритма сортировки – была одним из ключевых элементов его, казалось бы, естественной харизмы (которую на деле обеспечивала тщательная подготовка), отличавшей всю его кампанию и в конце концов приведшей его в Белый дом.

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

Существуют, однако, проблемы, которые просты в изложении, но для их решения может потребоваться астрономическое количество времени. Представьте, что вы работаете в крупной транспортной компании вроде DHL или UPS и за смену вам нужно доставить по разным адресам несколько посылок. Поскольку вам платят по количеству доставленных посылок, а не по времени, которое вы тратите на их доставку, вы хотите найти кратчайший маршрут между всеми пунктами доставки. В этом суть старой и важной математической головоломки – задачи коммивояжера. С ростом количества пунктов доставки сложность выбора оптимального маршрута растет лавинообразно – происходит так называемый комбинаторный взрыв. Вариативность маршрута с добавлением к нему новых локаций растет быстрее экспоненты. Если вы начнете с 30 адресов доставки, то у вас будет 30 вариантов выбора первой точки, 29 – второй, 28 – третьей и так далее. В общей сложности нужно будет проверить 30 × 29 × 28 ×… × 3 × 2 разных маршрута. Итого количество возможных маршрутов с 30 остановками составляет около 265 нониллионов – 265 с 30 нулями. Но на этот раз, в отличие от проблемы сортировки, у вас нет простого решения – практического алгоритма, решающего эту задачу в полиномиальном время, не существует. Проверить правильность решения так же сложно, как и найти его, поскольку проверять необходимо все возможные решения.

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

Единственное достоинство всех этих проблем заключается в том, что хорошие решения для некоторых таких задач мы можем распознать сразу, как только увидим. Если при формулировке проблемы ввести определенное условие – например, указать, что общая протяженность маршрута доставки не должна превышать 1000 миль, то адекватность предложенного решения мы сможем проверить сразу и легко, даже если найти такой маршрут очень трудно. Подобная задача так и называется – «задача принятия решения»; в нашем случае это проблема коммивояжера с задачей принятия решения, и она требует ответа «да» или «нет». Это один из типов проблем группы NP, для которого найти решение сложно, но проверить его легко.

Несмотря на отсутствие общего решения проблемы, для некоторых ее частных случаев (определенного множеств локаций и направлений) точные решения найти можно, хотя это и достаточно сложно. Билл Кук, профессор комбинаторики и оптимизации в Университете Ватерлоо в Онтарио, потратил почти 250 лет компьютерного времени на суперкомпьютере с параллельной архитектурой, вычисляя кратчайший маршрут между всеми пабами Соединенного Королевства. Этот мегазагул предусматривает посещение 49 687 заведений и имеет протяженность всего 40 тысяч миль – в среднем на один паб приходится 0,8 мили. Задолго до того, как Кук начал свои расчеты, Брюс Мастерс из Бедфордшира в Англии решал ту же проблему своим путем – эмпирическим. Ему принадлежит мировой рекорд Гиннесса (самая подходящая книга для такого рекорда) по посещению пабов. К 2014 году 69-летний рекордсмен выпивал в 46 495 различных заведениях. Начиная с 1960 года, по оценкам Брюса, он проехал и прошел более миллиона миль, чтобы посетить все пабы Великобритании – в 25 с лишним раз больше, чем самый эффективный маршрут Билла Кука. Если вы планируете отправиться в подобную одиссею или даже просто собираетесь прошвырнуться по местным пабам, вам, вероятно, стоит для начала свериться с алгоритмом Кука .

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

С другой стороны, тогда мы могли бы разработать быстрые алгоритмы для решения всевозможных логистических задач. Фабрики могли бы организовать производственный процесс с максимальной эффективностью, а службы доставки находили бы самые эффективные маршруты транспортировки, что потенциально снижало бы цену товара – даже если его больше нельзя было бы безопасно заказать онлайн! В научной сфере доказательство равенства P и NP может обеспечить эффективные методы машинного распознавания образов, генетического секвенирования и даже прогнозирования стихийных бедствий.

По иронии судьбы от равенства P и NP больше всего может выиграть наука, а вот сами ученые могут оказаться главными проигравшими. Некоторыми потрясающими научными открытиями человечество обязано прежде всего творческому мышлению высококвалифицированных и глубоко преданных своему делу людей: дарвиновская теория эволюции путем естественного отбора, доказательство Последней теоремы Ферма Эндрю Уайлсом, теория общей относительности Эйнштейна, ньютоновские уравнения движения. Если бы P равнялся NP, то компьютеры сумели бы найти формальные доказательства любой доказуемой математической теоремы – и многие из величайших интеллектуальных достижений человечества могли бы быть воспроизведены и вытеснены работой робота. Масса математиков остались бы без работы. По сути своей, проблема P vs NP – это очень непростая попытка выяснить, можно ли автоматизировать человеческое творчество.