Золотой билет. P, NP и границы возможного - Лэнс Фортноу

В теории сложности вычислений класс задач, для которых можно быстро проверить предполагаемое решение, обозначается NP (где N значит «недетерминированная машина Тьюринга», а P – «полиномиальное время», если уж вам так интересно). Наиболее известные представители класса NP – это как раз поиск клики, поиск гамильтонова пути, раскраска карт и построение максимального разреза.

Обратите внимание, что в классе P, в отличие от класса NP, решение можно быстро найти. Примеры – кратчайший путь, максимальное число паросочетаний, эйлеров путь (первая игра со скипетром) и минимальный разрез.

А что, если быстрый алгоритм поиска клики существует? Если в один прекрасный день какой-нибудь гениальный аспирант разработает простой метод нахождения гамильтонова пути, эффективный алгоритм раскраски карт или быстрый способ построения максимального разреза? Вдруг все эти проблемы на самом деле лежат в классе P – так же как и задачи о кратчайшем пути, максимальном числе паросочетаний, эйлеровом пути и минимальном разрезе? Такое вполне возможно; может даже оказаться, что быстрый алгоритм существует для всех задач из NP. Но пока мы этого не знаем.

В этом и заключается суть проблемы равенства (или неравенства) классов P и NP. Если P = NP, мы попадаем в совершенный мир, где для любой задачи из NP существуют эффективные алгоритмы, и можно не только быстро проверить предполагаемое решение, но и быстро найти самый оптимальный вариант. И наоборот – если найдется хоть одна задача из NP, для которой эффективного алгоритма не существует, это будет означать, что P ≠ NP.

Вопрос о равенстве P и NP – одна из центральных проблем вычислительной техники, а возможно, и всей математики. Многочисленные попытки ученых доказать равенство классов и разработать быстрые алгоритмы для поиска клики или гамильтонова пути, а также других NP-задач, успехом не увенчались. С неравенством классов дело обстоит еще сложнее: ведь для обоснования того факта, что P ≠ NP, нужно доказать невозможность построения быстрого алгоритма для клики или других задач из NP. Но как вы докажете невозможность чего бы то ни было? До сих пор ни в том, ни в другом направлении не было получено сколько-нибудь значимых результатов. Проблема P и NP настолько важна, что Математический институт Клэя предложил миллион долларов за ее решение. А я загорелся идеей написать эту книгу.

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

Геном человека содержит двадцать три пары хромосом, каждая из которых представляет собой двойную цепочку пар оснований. Основания бывают четырех видов – аденин (A), цитозин (C), гуанин (G) и тиамин (T). Цепочки начинаются примерно так: «ACTGATTACA…»; некоторые достигают прямо-таки гигантских размеров. Самая короткая хромосома содержит около 47 миллионов пар оснований, а самая длинная – около 247 миллионов. Современные методы секвенирования ДНК позволяют за один прием обрабатывать участки длиной от 20 до 1000 пар оснований. Ученым приходится секвенировать огромное число коротких кусков, а потом придумывать, как их лучше соединить. Склейка последовательности – задача огромной вычислительной сложности и принадлежит она классу NP: ведь, имея на руках готовую последовательность, можно относительно быстро определить, складывается она из секвенированных участков или нет. Поскольку эффективные методы для поиска оптимального решения пока неизвестны, биологи при составлении карты человеческого генома вынуждены секвенировать избыточное число последовательностей; к сожалению, это не слишком спасает их от ошибок и неясных мест, которых при наличии хорошего алгоритма было бы гораздо меньше.

Последовательности ДНК содержат закодированную информацию о последовательностях матричных РНК, а те, в свою очередь, хранят информацию о синтезе белков. Белки – или, иначе, протеины – играют ключевую роль в работе клеток, формирующих любой живой организм. Для выполнения своих функций протеин должен особым образом свернуться, т. е. принять определенную пространственную форму. Сложный механизм сворачивания биологами пока не разгадан; известно только, что процессом командуют матричные РНК. Решение проблемы равенства P и NP помогло бы продвинуться на пути понимания этого механизма и, как следствие, – лечения и предотвращения болезней.

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

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

Рис. 3.17. Простейшая физическая система

Рассмотрим простейшую физическую систему: шарик на неровной поверхности (рис. 3.17). При x = 3,0 уровень потенциальной энергии шарика минимален, а при x = 1,0 – нет, хотя шарик будет оставаться в этой точке до тех пор, пока его не толкнут. Таким образом, состояние покоя еще не гарантирует минимального уровня энергии. Поиск состояния минимальной энергии для сложных физических систем – задача чрезвычайно трудная, с которой подчас не справляются не только компьютеры, но и сами физические системы.

С некоторыми особо трудоемкими NP-задачами можно бороться при помощи квантовой механики; подробнее об этом вы узнаете в девятой главе.

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

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