Впервые проблема равенства классов упоминается еще в 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, т. е. в наибольшую по численности группу, в которой все дружны между собой? Может, сотня? А может быть, тысяча? Даже при наличии доступа ко всем необходимым данным ответить на этот вопрос будет крайне непросто; искать максимальную клику не легче, чем возиться с какой-нибудь другой поисковой проблемой.

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

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

Какова предыстория проблемы равенства P и NP? На самом деле здесь не одна история, а целых две. События разворачивались в те времена, когда Холодная война разделила мир на противоборствующие лагеря; понятие эффективных вычислений и связанные с ним вопросы независимо разрабатывались по разные стороны «железного занавеса». В итоге оба пути сошлись в одной точке, и эта точка получила имя «P против NP».

С какой стороны зайти, чтобы вывести неравенство P ≠ NP? Курт Гёдель показал, что не у всех математических проблем имеется решение; возможно, аналогичным образом удастся доказать тот факт, что не для всех поисковых задач существует быстрый алгоритм. Еще вариант – попытаться разделить вычислительный процесс на более мелкие части, чтобы сложность исходной задачи было легче оценить. Некоторую надежду дает также алгебраическая геометрия – молодой и абсолютно абстрактный раздел математики. Впрочем, до решения проблемы мы в любом случае дойдем еще очень не скоро.

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

Изменят ли ситуацию компьютеры будущего, основанные на принципах квантовой механики? Снимут ли они проблему «P против NP»? Маловероятно, хотя с их помощью мы сможем решать некоторые недоступные современным машинам задачи, например, раскладывать большие числа на множители. Кстати, квантовая механика даст нам абсолютно стойкие шифры вне зависимости от того, равны классы P и NP или не равны.

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

Упомянутые ранее тридцать восемь чисел

14175, 15055, 16616, 17495, 18072, 19390, 19731, 22161, 23320, 23717, 26343, 28725, 29127, 32257, 40020, 41867, 43155, 46298, 56734, 57176, 58306, 61848, 65825, 66042, 68634, 69189, 72936, 74287, 74537, 81942, 82027, 82623, 82802, 82988, 90467, 97042, 97507, 99564

можно разбить на две равные группы следующим образом:

15055, 16616, 19390, 22161, 26343, 40020, 41867, 43155, 46298, 57176, 58306, 65825, 66042, 69189, 74537, 81942, 82623, 82988, 90467