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

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

Когда в 1852 году английский (а впоследствии южноафриканский) математик Франсис Гатри раскрашивал карту графств Англии, ему пришло в голову, что любую карту можно раскрасить в четыре цвета таким образом, чтобы любые две смежные области получили разные цвета. Его гипотеза широко обсуждалась в математической среде; через некоторое время появились целых два доказательства: первое в 1879 году выдвинул Альфред Кемпе, второе – годом позже – Питер Тэт. Оба были опровергнуты, хотя второе продержалось одиннадцать лет, прежде чем в нем нашлись существенные изъяны. После этого проблема раскраски карт почти сто лет оставалась открытой.

Наконец, в 1976 году математики Кеннет Аппель и Вольфганг Хакен сумели доказать, что для правильной раскраски хватит четырех цветов. Правда, способ доказательства был довольно спорным: для проверки многочисленных примеров, на которых строились рассуждения, ученые использовали компьютер. Консервативно настроенные математики такой метод не приняли, поскольку не все его этапы можно было проверить вручную. Впрочем, формально доказательство Аппеля–Хакена так и не было опровергнуто, и сегодня уже мало кто сомневается в том, что любую карту действительно можно правильно раскрасить в четыре цвета.

А вдруг четыре – это не предел? Можно ли обойтись всего тремя цветами? Оказывается, нельзя, и сейчас мы с вами в этом убедимся. Давайте рассмотрим штат Невада и всех его соседей.

Неваду окружает кольцо из пяти штатов: Калифорния, Орегон, Айдахо, Юта и Аризона. Пять – число нечетное, поэтому для раскраски штатов кольца потребуется не менее трех цветов. Действительно, предположим, что цветов у нас всего два, к примеру – голубой и зеленый. Покрасим Калифорнию зеленым, соседний с ней Орегон – голубым, Айдахо – зеленым, и Юту – голубым. Осталась Аризона, которая граничит и с зеленой Калифорнией, и с голубой Ютой, так что мы не можем покрасить ее ни в зеленый цвет, ни в голубой. Следовательно, для раскраски всех пяти штатов кольца нужно как минимум три цвета. Пусть Аризона будет желтой.

Рис. 3.14. Невада и ее соседи

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

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

Начались поиски решения. Через некоторое время, так и не добившись результата, исследователи вынуждены были признать, что они не в состоянии найти способ раскрасить дома в три цвета. Правительству пришлось закупать краски четырех цветов; с тех пор институту уже нечасто удавалось выбить себе грант.

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

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

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

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

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

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

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

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

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