Величайшие математические задачи - читать онлайн книгу. Автор: Йен Стюарт cтр.№ 71

Определение Кука подразумевает, что все 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 лет спустя.

Пять из семи задач тысячелетия, включая и три задачи, о которых мы уже говорили, относятся к чистой математике, хотя задача P/NP фундаментальна и для теории вычислительных систем. Оставшиеся две принадлежат к прикладной математике и современной математической физике. Задача из прикладной математики возникает из стандартного уравнения для потока жидкости — уравнения Навье — Стокса, названного в честь французского инженера и физика Клода-Луи Навье и ирландского математика и физика Джорджа Стокса. Уравнение Навье — Стокса — это уравнение в частных производных; следовательно, в нем учитывается скорость изменения характера потока как в пространстве, так и во времени. Большинство важнейших уравнений классической прикладной математики — это уравнения в частных производных (нам уже встречалось одно из таких уравнений — уравнение Лапласа); остальные — обыкновенные дифференциальные уравнения, учитывающие скорость изменения параметров только во времени.

В главе 8 мы видели, что движение тел в Солнечной системе определяется законом всемирного тяготения и законами динамики Ньютона. Эти законы связывают ускорение Солнца, Луны и планет с действующими на них гравитационными силами. Ускорение — это быстрота изменения скорости во времени, а скорость — характеристика изменения положения тела во времени. Это обычное дифференциальное уравнение. Как мы видели, решение таких уравнений может быть очень сложным делом. Как правило, решать дифференциальные уравнения в частных производных намного сложнее.

Если говорить о практических целях, то уравнения движения в Солнечной системе могут быть решены численно при помощи компьютеров. Это тоже непросто, но сегодня уже существуют хорошие методы. То же самое можно сказать и о решении в практических целях уравнений Навье — Стокса. Используемые при этом методики известны как вычислительная гидрогазодинамика и применяются для решения многих важных задач: конструирования самолетов, расчета аэродинамики автомобилей и даже в медицине (например, для расчета тока крови в организме человека).

Задача тысячелетия не просит математиков найти явные решения уравнения Навье — Стокса, поскольку это, по существу, невозможно. Не имеет она отношения и к численным методам решения этих уравнений, несмотря на всю их важность. Вместо этого в задаче требуется найти доказательство фундаментального теоретического свойства: существования решений. При заданном состоянии жидкости в определенный момент времени — при известных характеристиках ее движения — существует ли решение уравнения Навье — Стокса, верное для всего будущего времени начиная с рассматриваемого момента? Интуиция подсказывает, что ответ на этот вопрос должен быть «да», потому что данное уравнение — очень точная модель физики реальной жидкости. Однако с точки зрения математики вопрос существования решения не так очевиден, и это фундаментальное свойство для уравнения Навье — Стокса пока не доказано. А возможно, ответ все же «нет», и решения не существует.