Проблема «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 нулями. Но на этот раз, в отличие от проблемы сортировки, у вас нет простого решения – практического алгоритма, решающего эту задачу в полиномиальном время, не существует. Проверить правильность решения так же сложно, как и найти его, поскольку проверять необходимо все возможные решения.
