Золотой билет - [4]

Впервые проблема равенства классов упоминается еще в 1956 году – в письме, которое один величайший математик XX века, Курт Гёдель, отправил другому величайшему математику XX века, Джону фон Нейману. К сожалению, вплоть до восьмидесятых о письме ничего не было известно, а вот первые официальные публикации появились в начале семидесятых. Авторы – Стивен Кук и Леонид Левин – независимо друг от друга пришли к одному и тому же вопросу, находясь по разные стороны «железного занавеса». Вслед за этим Ричард Карп опубликовал свой знаменитый список из двадцати одной задачи: все они, включая маршрут для коммивояжера и разбиение на группы, были эквивалентны проблеме «P против NP». Постепенно научное сообщество осознало важность поднятых вопросов, и в развитии информатики наступил поворотный момент. Сейчас проблема равенства классов уже стала основополагающей – причем не только в информатике, но также в биологии, медицине, экономике, физике и многих других областях.

Со временем этот вопрос заработал статус одной из самых трудных задач в истории математики. Шумиха вокруг доказательства Великой теоремы Ферма, предложенного в 1994 году Эндрю Уайлсом, побудила Математический институт Клэя организовать нечто вроде конкурса по решению сложнейших открытых математических проблем. В 2000 году институт опубликовал список из семи «задач тысячелетия» и за каждую из них объявил награду в один миллион долларов. Вот они:

1. Гипотеза Берча–Свиннертон–Дайера.

2. Гипотеза Ходжа.

3. Уравнения Навье–Стокса.

4. Проблема равенства P и NP.

5. Гипотеза Пуанкаре.

6. Гипотеза Римана.

7. Теория Янга–Миллса.

Гипотезу Пуанкаре в 2003 году доказал Григорий Перельман, однако от вознаграждения ученый отказался. Остальные шесть задач тысячелетия на момент написания книги по-прежнему остаются открытыми.

Решите проблему «P против NP» – и получите настоящий золотой билет, т. е. миллион долларов США!

Лучше всего, конечно, если вы установите равенство P и NP: тогда у вас будет алгоритм для поиска всех золотых билетов (т. е. решения всех остальных задач из списка). Докажете, что P = NP, – получите шесть миллионов за решение шести задач тысячелетия. Впрочем, доказать как равенство, так и неравенство классов будет очень и очень непросто; если вам нужны шесть миллионов, вы скорее выиграете их в лотерею.

В поисках билета

Иногда найти билет все же удается. Предположим, мне нужно поехать из Чикаго в Нью-Йорк на машине. Не долго думая, я забиваю адрес в навигатор, который уже через минуту-другую показывает оптимальный маршрут, и жму на газ. Подробная карта США со всеми городами и улицами занимает миллионы байт; возможные маршруты исчисляются гораздо более крупными цифрами. Сколько маршрутов можно проложить из Чикаго в Нью-Йорк? Грубейший подсчет даст нам свыше вигинтиллиона (единица и 63 нуля) вариантов, и запрет движения по встречке на односторонних улицах мало что изменит. У навигатора просто нет времени на такое количество проверок; как же он умудряется найти самый быстрый маршрут?

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

Именно так и сужают круг поиска навигационные программы. Десять тысяч или даже сто тысяч вариантов – это уже не вигинтиллион; современный процессор проверит их без труда.

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

Долгая дорога

Эта книга расскажет вам захватывающую историю о P и NP. Что это за классы? Какая между ними разница? Что такое NP-полные, или самые трудные, поисковые задачи? Как они связаны с проблемой P и NP?

Для наглядности приведу один маленький пример. Сколько человек входит в максимальную клику на Facebook, т. е. в наибольшую по численности группу, в которой все дружны между собой? Может, сотня? А может быть, тысяча? Даже при наличии доступа ко всем необходимым данным ответить на этот вопрос будет крайне непросто; искать максимальную клику не легче, чем возиться с какой-нибудь другой поисковой проблемой.

Какая перспектива ожидает нас, если классы равны? Совершенный мир, в котором все можно вычислить быстро. Ответы на вопросы будут приходить почти мгновенно; смертельных болезней не останется, и вселенная раскроет нам все свои тайны. Однако есть здесь и своя ложка дегтя: с компьютерами, которые могут почти все, нас ждет безработица и потеря конфиденциальности.

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