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

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

и 14175, 17495, 18072, 19731, 23320, 23717, 28725, 29127, 32257, 56734, 61848, 68634, 72936, 74287, 82027, 82802, 97042, 97507, 99564.

Числа каждой группы дают в сумме ровно 1000000.