Величайшие математические задачи

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

Чтобы представить себе характер этой процедуры, рассмотрим типичную NP-полную задачу: поиск гамильтонова цикла в сети. Требуется найти замкнутый маршрут по ребрам сети, которые прошел бы через каждый узел (т. е. через каждую точку) ровно один раз. «Замкнутый» означает, что в конце концов маршрут возвращается в начальную точку. Размер входных данных здесь — это число ребер, меньшее или равное квадрату числа точек, поскольку каждое ребро соединяет две точки. (Считаем, что любую заданную пару соединяет не больше одного ребра.) Нам не известно ни одного алгоритма класса P, который решал бы эту задачу, но предположим — гипотетически, — что такой алгоритм существует. Теперь выберем какую-нибудь другую задачу и назовем ее задачей X. Пусть задача X может быть переформулирована в терминах поиска такого маршрута в некоей сети, связанной с задачей X. Если метод перевода данных задачи X в данные об этой сети и наоборот, может быть применен за полиномиальное время, то мы автоматически получаем алгоритм класса P для задачи X. Примерно так:

1. Переводим задачу X в задачу поиска гамильтонова цикла в связанной с задачей сети. Это можно сделать за полиномиальное время.

2. Находим такой цикл за полиномиальное время при помощи того самого гипотетического алгоритма для задачи с сетью.

3. Переводим полученный гамильтонов цикл обратно в решение задачи X, что опять же можно проделать за полиномиальное время.

Поскольку все три полиномиальных шага вместе можно проделать тоже за полиномиальное время, этот алгоритм относится к классу P.

Чтобы показать, как это работает, я рассмотрю менее амбициозную версию задачи о поиске гамильтонова цикла, где искомый маршрут не обязан быть замкнутым. В таком виде она называется задачей о поиске гамильтонова пути. Сеть может иметь гамильтонов путь и при этом не иметь цикла (см. пример на рис. 42 слева). Так что решение задачи о поиске гамильтонова цикла может не означать решения задачи о поиске гамильтонова пути. Однако задачу о поиске гамильтонова пути можно переформулировать в задачу о поиске гамильтонова цикла на близкой, но несколько иной сети. Для этого в сеть добавляется одна дополнительная точка, соединенная со всеми точками первоначальной сети, как на рис. 42 справа. Любой гамильтонов цикл в новой сети может быть превращен в гамильтонов путь: для этого достаточно исключить из него добавленный узел и два подходящих к нему ребра цикла. И наоборот, любой гамильтонов путь в первоначальной сети дает цикл в новой: достаточно просто соединить два конца пути с новой точкой. Это «превращение» задачи о поиске пути в задачу о поиске цикла вводит в сеть всего одну новую точку и по одному ребру на каждую точку первоначальной сети, так что эта процедура — и обратная ей тоже — выполняется за полиномиальное время.

Конечно, я здесь всего лишь зашифровал одну конкретную задачу, превратив ее в задачу о поиске гамильтонова цикла. Чтобы доказать, что такая задача является NP-полной, нам нужно проделать то же самое с любой NP-задачей. Это реально: первое доказательство нашел Ричард Карп в 1972 г. в знаменитой статье, где доказывалась NP-полнота 21 различной задачи.

Задача о коммивояжере является «почти» NP-полной, но здесь есть одна техническая сложность: мы не знаем, относится ли она к классу NP. Известно более 300 конкретных NP-полных задач в различных областях математики, включая логику, теорию графов, комбинаторику и оптимизацию. Доказать, что любая из них может (или не может) быть решена за полиномиальное время, означало бы доказать то же для всех них без исключения. Несмотря на богатство выбора, задача P/NP по-прежнему остается открытой. И я бы не удивился, если бы узнал, что она останется таковой и 100 лет спустя.

12. Потоковое мышление. Уравнение Навье — Стокса