Читать «Золотой билет» онлайн - страница 30

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

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

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

P против NP

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

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

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

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