Текст книги "Золотой билет. P, NP и границы возможного"

На первый-второй рассчитайсь!

В Королевской начальной школе обучается 500 детей. Преподаватели решили поделить их на две группы, разлучив при этом как можно меньшее число друзей, поскольку те, конечно, хотели оставаться вместе. Вернемся к схеме дружеских связей, рассмотренной в игре со скипетром.

Рис. 3.15. Младшеклассники

Наилучшим решением будет поместить Алекса и Кэти в одну группу, а Барбару, Дэвида и Эрика – в другую: так мы разорвем всего две дружеские связи, Алекс-Эрик и Кэти-Эрик. Очевидно, что разбиения, которое разлучило бы лишь одну пару друзей, просто не существует.

Рис. 3.16. Группы младшеклассников

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

Все были довольны и счастливы… до тех пор, пока учителя не осознали, что помещать в одну группу врагов – это еще хуже, чем разлучать друзей. И директору снова пришлось идти в институт. Теперь он просил составить группы таким образом, чтобы разделить как можно большее число врагов. Первая задача не вызвала абсолютно никаких затруднений, и директору казалось, что со второй задачей в институте справятся с такой же легкостью… однако он ошибался.

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

В конце концов выход все же нашелся. Применив алгоритм, разработанный в 1995 году Мишелем Гемансом и Дэвидом Уильямсоном, исследователи сумели построить такое разбиение, при котором в разные группы попадала 1321 пара врагов. Максимальный разрез построить не удалось, однако до него оставалось совсем немного: исследователи знали, что не существует такого разбиения, при котором «разрезалось» бы более 1505 вражеских связей. Директор остался несколько разочарован тем, что оптимальное решение так и не нашли, но ему пришлось смириться. Теперь все снова были довольны и счастливы. Надолго ли?..

P против NP

Некоторые задачи заставили институтских исследователей изрядно попотеть. Давайте их перечислим: поиск клики, поиск гамильтонова пути (вторая игра со скипетром), раскраска карт и построение максимального разреза. У всех этих задач есть одна общая черта: для них легко проверить, является ли найденное решение верным. Зная всех членов общества «Альфа», можно без особых затруднений убедиться в том, что все они дружат между собой, а следовательно – образуют клику. Предполагаемое решение игры «Передай скипетр – 2» можно легко протестировать, просто начав в нее играть. Когда все дома раскрашены, можно за вполне разумное время проверить, что цвета любых двух соседних домов различаются. И, наконец, когда ученики уже разбиты на две группы, директор школы легко подсчитает число разорванных вражеских связей.

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

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

В 1928 году выдающийся немецкий математик Давид Гильберт сформулировал свою знаменитую проблему разрешимости – Entscheidungsproblem: существует ли универсальный алгоритм, который для любого математического утверждения определяет, истинно оно или ложно? В 1931 году Курт Гёдель показал, что некоторые утверждения невозможно доказать или опровергнуть ни в одной системе аксиом; спустя несколько лет вдохновленные его результатами Алонзо Чёрч и Алан Тьюринг независимо друг от друга доказали, что универсального алгоритма не существует.

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

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

Решение головоломки «Путешествие по додекаэдру»

Рис. 3.18. Обход додекаэдра

Глава 4. Самые трудные задачи класса NP

Психолог проводит эксперимент над математиком. Математика посадили в маленький деревянный сарай; на полу лежит лучина для растопки, рядом стоит стол, а на нем – ведро с водой. Психолог поджигает лучину. Математик хватает ведро и заливает огонь водой.

Пока все идет по плану. Психолог повторяет эксперимент, изменив одну незначительную деталь. Математика снова сажают в сарай; внутри тот же стол, на полу такая же лучина, есть и ведро с водой, но стоит оно не на столе, а рядом с лучиной на полу. Психолог поджигает лучину. Математик хватает ведро и ставит его на стол. В результате сарай выгорел дотла; математика, к счастью, успели в последний момент вытащить.

«Почему вы просто не залили огонь?!» – спрашивает психолог. «Я свел новую задачу к уже решенной», – отвечает математик.

Старый математический анекдот

Первая NP-полная задача

В 1970 году Том Хал, глава факультета информатики Университета Торонто, загорелся идеей переманить к себе Стивена Кука, которому не хотели давать постоянное место в Калифорнийском университете в Беркли. Зная любовь Кука к парусному спорту, Хал отвез его на озеро Онтарио: он хотел доказать, что в окрестностях Торонто ходить под парусом почти так же приятно, как и в заливе Сан-Франциско. Хитрость удалась, и осенью 1970 года Кук пополнил ряды специалистов Торонтского университета. Со стороны Хала это был блестящий ход, поскольку в скором времени Кук прославился на весь мир и стал самым известным канадским ученым в области теории вычислений.

Кук проводил исследования на стыке математической логики и теоретической информатики. Той осенью он отправил одну из своих работ на рассмотрение комиссии III Международного симпозиума по теории вычислений (Symposium on the Theory of Computing, сокращенно – STOC), проводимого Ассоциацией вычислительной техники. Симпозиум должен был состояться в мае 1971 года. В статье Кука содержались результаты, полученные им задолго до того и не вызвавшие в свое время ажиотажа. Исследования ученого заинтересовали комиссию, и заявку приняли. К началу конференции Кук почти все переделал; в новой статье, которая называлась The Complexity of Theorem-Proving Procedures, он впервые сформулировал проблему равенства классов P и NP и тем самым полностью изменил ход истории.

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

Рис. 4.1. Задача о клике

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

Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе».

«ИЛИ» здесь не исключающее: возможен вариант, при котором ни Алекс, ни Дэвид не входят в сообщество. Алекс и Барбара тоже враждуют, а следовательно – не могут оба входить в «Альфу». Запишем и это:

Алекс не в «Альфе» ИЛИ Барбара не в «Альфе».

Оба утверждения должны выполняться одновременно, а значит, мы имеем:

(Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе»)

И

(Алекс не в «Альфе» ИЛИ Барбара не в «Альфе»).

Барбара и Дэвид – друзья, поэтому они вполне могут одновременно входить в «Альфу», и построенное нами выражение такой возможности не исключает. Проанализировав всю схему, мы в итоге получим следующее выражение:

(Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе») И (Алекс не в «Альфе» ИЛИ Барбара не в «Альфе») И (Дэвид не в «Альфе» ИЛИ Кэти не в «Альфе») И (Кэти не в «Альфе» ИЛИ Барбара не в «Альфе»).

Допустим, Алекс, Кэти и Эрик принадлежат сообществу, а Барбара и Дэвид – нет; тогда наше выражение истинно, так как в каждом условии «ИЛИ» упоминается кто-то, кто в «Альфу» не входит. Теперь предположим, что сообществу принадлежат Алекс, Дэвид и Эрик. Тогда условие (Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе») не выполняется, поскольку и Алекс, и Дэвид входят в сообщество, а значит – ложно и все выражение.

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

Аналогичную конструкцию можно составить и для всех 20 тысяч жителей Королевства. В результате получится огромное, содержащее несколько миллионов символов выражение – впрочем, не настолько длинное, чтобы не уместиться в компьютер. Для краткости обозначим его буквой Φ. Очевидно, что Φ будет истинно только тогда, когда «альфовцы» в самом деле образуют клику.

Через Ψ50 обозначим выражение, истинное в том случае, если в «Альфу» входят хотя бы 50 человек. Не будем углубляться в его структуру; достаточно будет сказать, что построить его можно тем же способом, каким первые цифровые компьютеры выполняли сложение чисел.

Соединим наши выражения в одно: (Ψ50 И Φ). Если члены сообщества образуют клику размером не меньше 50, то новое выражение примет значение «истина», и наоборот – если выражение истинно, то члены сообщества образуют клику размером не меньше 50.

Логическое выражение, проверяющее принадлежность к сообществу, называется выполнимым, если сообщество можно составить таким образом, что выражение примет значение «истина». Выражение (Ψ50 И Φ) выполнимо, когда в сообществе есть клика размера не меньше 50.

Предположим, у нас есть быстрый алгоритм, проверяющий выполнимость логического выражения. Подадим ему на вход выражение (Ψ50 И Φ); если алгоритм ответит «да», то в Королевстве существует клика размера 50, а если «нет» – то не существует. Таким образом, алгоритм решения задачи о выполнимости позволяет решить и задачу о клике.

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

На самом деле к проблеме выполнимости, или SAT (от англ. satisfiability – выполнимость), сводится не одна лишь задача о клике, но и другие задачи класса NP, которые мы обсуждали ранее, включая задачу о коммивояжере, поиск гамильтонова пути, построение максимального разреза и раскраску карт. Стивен Кук доказал, что любая проблема из NP сводится к проблеме выполнимости. Решите проблему выполнимости – и у вас будет ключ ко всем проблемам из NP. Появление эффективного алгоритма для задачи о выполнимости будет означать, что такой алгоритм существует для всех задач, решение которых легко проверяется, а следовательно, P = NP. Создайте эффективный алгоритм решения проблемы SAT – и получите миллион долларов от Института Клэя!

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

Симпозиум проходил в городке Шейкер-Хайтс в штате Огайо, в отеле Somerset Inn, принадлежащем компании Stouffer. Стивен Кук выступил с докладом 4 мая 1971 года.

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

С того дня и ведет свою историю проблема равенства P и NP.