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

Возьмем для примера подробно разобранную Куком задачу о выполнимости и рассмотрим случай с двадцатью переменными. Применим к ней простейший алгоритм, который методично перебирает все возможные комбинации значений переменных, устанавливая их в TRUE или FALSE. Если предположить, что на обработку одной комбинации уходит 100 шагов, то выполнимость всей формулы будет проверяться примерно 19 минут. Долго, конечно, но ведь могло быть и хуже! Однако проблема в том, что с двадцатью переменными каши особо не сваришь.

Двадцать пять переменных обрабатывались бы примерно 10 часов. Тридцать – чуть больше 13 суток. Ну а с сорока переменными мы бы ждали с 1971-го года по 2009-й.

Сейчас Intel каждый год выпускает несколько новых моделей процессоров. Рассмотрим, к примеру, появившийся в 2009-м Intel i7–870, который мог выполнять 2,93 миллиарда операций в секунду – в 30000 раз больше, чем Intel 4004. С сорока переменными он справился бы часов за десять, так что в 1971-м быстрее было бы просто подождать 38 лет и воспользоваться технологиями 2009-го.

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

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

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

Рис. 6.1. Коммивояжер: города с населением более 500 человек

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

Любой вычислительный алгоритм – это тоже метод решения какого-либо вопроса. Эвристические алгоритмы работают подобно правилу большого пальца: иногда они ошибаются, однако в большинстве случаев находят верное решение. Для NP-полных задач такие алгоритмы начали появляться задолго до того, как об их NP-полноте стало известно. За последние десятилетия сложными эвристическими методами «обзавелось» огромное множество трудоемких задач. Ни один из этих методов не является универсальным и не годится для всех случаев сразу, однако в общем и целом они со своей работой справляются.

Рис. 6.2. Карта Соединенных Штатов

Давайте подробно рассмотрим простой, но очень мощный эвристический алгоритм раскраски карт. В третьей главе мы объяснили, почему для правильной раскраски карты Соединенных Штатов, т. е. для раскраски, при которой соседние штаты имеют разные цвета, требуется не меньше четырех цветов.

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

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

На рисунке ниже представлена карта областей Армении.

Всего две из них целиком лежат внутри страны. Котайк окружен шестью областями, а столица Ереван – четырьмя. Эвристический метод говорит нам, что если все внутренние регионы имеют четное число соседей, то для раскраски карты хватит трех цветов. И мы видим, что для Армении так и получается.

Швейцарию окружает нечетное число соседей – пять. Это Франция, Италия, Австрия, Лихтенштейн и Германия. Несмотря на это, карту на рис. 6.5 тоже можно раскрасить в три цвета.

Дело в том, что Лихтенштейн вклинился между Швейцарией и Австрией и разбил их общую границу на две, поэтому Австрию нужно учитывать дважды. Оказывается, важно не количество соседних государств, а количество общих границ; у Швейцарии их шесть, а шесть – число четное. Заметим, что считаются только внешние границы, и страны, целиком лежащие внутри другого государства, не учитываются вообще (например, Ватикан внутри Италии).

Рис. 6.3. Армения

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

Эвристический метод имеет ровно два исключения.

1. На карте имеется озеро, по которому проходит граница между регионами. Например, озеро Мичиган отделяет Иллинойс от штата Мичиган.

Рис. 6.4. Раскраска Армении

2. Четыре или более регионов встречаются в одной точке. Например, Аризона, Нью-Мексико, Колорадо и Юта.

Впрочем, в случае с США исключения роли не играют, поскольку мы и так уже знаем, что цветов нужно четыре (не считая, разумеется, синего для озер).

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