Лэнс Фотноу - Золотой билет
Неваду окружает кольцо из пяти штатов: Калифорния, Орегон, Айдахо, Юта и Аризона. Пять – число нечетное, поэтому для раскраски штатов кольца потребуется не менее трех цветов. Действительно, предположим, что цветов у нас всего два, к примеру – голубой и зеленый. Покрасим Калифорнию зеленым, соседний с ней Орегон – голубым, Айдахо – зеленым, и Юту – голубым. Осталась Аризона, которая граничит и с зеленой Калифорнией, и с голубой Ютой, так что мы не можем покрасить ее ни в зеленый цвет, ни в голубой. Следовательно, для раскраски всех пяти штатов кольца нужно как минимум три цвета. Пусть Аризона будет желтой.
Рис. 3.14. Невада и ее соседи
Невада имеет общие границы со всеми перечисленными штатами, а значит, мы не можем покрасить ее ни зеленым, ни голубым, ни желтым, и для правильной раскраски требуется четвертый цвет.
На базе доказательства теоремы о четырех красках были разработаны алгоритмы, позволявшие правильно раскрашивать карты четырьмя цветами за приемлемое время. Основываясь на этих алгоритмах, в институте создали такую схему раскраски, в которой любые два соседних дома получали разные цвета. Цветов было всего четыре, однако правительство потребовало сократить их число до трех. Доказать, что это невозможно, исследователи не сумели, поскольку на всей территории Королевства не нашлось ни одного дома, окруженного нечетным числом соседей. Отвертеться от задания не удалось.
Начались поиски решения. Через некоторое время, так и не добившись результата, исследователи вынуждены были признать, что они не в состоянии найти способ раскрасить дома в три цвета. Правительству пришлось закупать краски четырех цветов; с тех пор институту уже нечасто удавалось выбить себе грант.
На первый-второй рассчитайсь!
В Королевской начальной школе обучается 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: ведь, имея на руках готовую последовательность, можно относительно быстро определить, складывается она из секвенированных участков или нет. Поскольку эффективные методы для поиска оптимального решения пока неизвестны, биологи при составлении карты человеческого генома вынуждены секвенировать избыточное число последовательностей; к сожалению, это не слишком спасает их от ошибок и неясных мест, которых при наличии хорошего алгоритма было бы гораздо меньше.
