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

АКТ БОТ ДОМ РОГ

АКТ БОТ ДОМ РОГ

АКТ БОТ ДОМ РОГ

На четвертом проходе ничего не происходит, так что мы понимаем, что программа завершила работу. Обратите внимание, как слово АКТ постепенно всплывает вверх (т. е. к началу списка).

Если в списке четыре слова, алгоритм на каждом шагу проводит три сравнения, а всего шагов получается четыре. Если слов в списке n, то на каждом проходе проводится n − 1 сравнение, а проходов необходимо n, так что всего требуется n (n − 1) шагов. Это чуть меньше, чем n², так что время работы программы полиномиально, более того, квадратично. Алгоритм может прекратить работу раньше, но в самом худшем случае, если окажется, что слова в списке стоят точно в обратном порядке, ему потребуется n (n − 1) шагов. Пузырьковый алгоритм сортировки очевиден и относится к классу P, но это далеко не самый эффективный алгоритм. Самый быстрый алгоритм сортировки — алгоритм сравнения — организован более хитро и выполняется за nlogn шагов.

Простой алгоритм с экспоненциальным временем работы — алгоритм класса E — это, к примеру, задание «распечатать список всех n-значных двоичных чисел». В таком списке 2n чисел, и на печать (и вычисление) каждого уходит примерно n шагов, так что полное время работы составляет приблизительно 2nn, что больше, чем 2n, но меньше, чем 3n для достаточно больших n. Однако это довольно глупый пример, поскольку медленным его делает не сложность вычислений, а всего лишь размер выходных данных, и позже это наблюдение окажется весьма важным.

Более типичный алгоритм класса E решает задачу о коммивояжере. Этот странствующий продавец должен посетить некоторое количество городов. Делать это он может в произвольном порядке. Какой путь следует избрать, чтобы суммарное расстояние оказалось минимальным? Наивный способ решения этой задачи состоит в том, чтобы выписать все возможные маршруты, рассчитать для каждого суммарное расстояние и найти минимальное из всех. Для n городов у нас получится

n! = n (n — 1) × (n — 2) × … × 3 × 2 × 1

маршрутов (читается «n факториал»). Эта величина растет быстрее, чем любая экспоненциальная величина{37}. Более эффективный метод, известный как динамическое программирование, позволяет решить задачу о коммивояжере за экспоненциальное время. Первый подобный метод — алгоритм Хелда — Карпа — находит кратчайший маршрут за 2nn2 шагов; при достаточно больших n это опять же попадает в интервал между 2n и 3n.

Несмотря на то что эти алгоритмы «неэффективны», при помощи специальных уловок можно ускорить расчет в случае, если число городов велико по человеческим меркам, но не слишком велико для применения подобных хитростей. В 2006 г. Д. Эпплгейт, Р. Биксби, В. Шваталь и У. Кук решили задачу о коммивояжере для 85 900 городов. На середину 2012 г. это достижение все еще оставалось рекордным.

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

Можно вспомнить все ту же вторую главу. Пока команда Агравала не придумала свой алгоритм класса P для проверки на простоту, наилучший известный алгоритм принадлежал классу не-P. Тем не менее он тоже был достаточно хорош, считал за время nlogn для n-значных чисел, а это, вообще говоря, лучше, чем показатели алгоритма Агравала — Каяла — Саксены, пока мы не достигаем чисел с 101000 знаками. До открытия этого алгоритма мнения о статусе испытания на простоту разделялись. Некоторые специалисты считали, что это задача класса P и подходящий алгоритм рано или поздно будет найден. Другие были уверены, что этого не произойдет. Новый алгоритм возник практически ниоткуда: его породила одна из бесчисленных идей, которые можно было попробовать, и данная конкретная идея сработала. Это отрезвляющий прецедент: мы не знаем истинного положения вещей, не можем предсказать его заранее, и догадки лучших экспертов могут быть как верными, так и ошибочными.

Великая задача, которая нас в данный момент интересует, заключается в поиске ответа на более фундаментальный вопрос. Существуют ли сложные задачи? Могут ли все задачи оказаться простыми, если, конечно, приложить достаточно ума и сообразительности? На самом деле здесь есть одна тонкость, потому что мы уже видели одну несомненно сложную задачу: распечатку списка всех n-значных двоичных чисел. Я уже упоминал о том, что это глупый пример: сложность заключается не в расчетах, а в простой монотонной работе по распечатке очень длинного ответа. Нам известно, что никакие уловки здесь не помогут, поскольку ответ будет таким длинным по определению. Если бы он был короче, он не был бы ответом.

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

Слово «недетерминированный» здесь используется потому, что существует возможность решить NP-задачу при помощи просто вдохновенной догадки. Сделав это, можно проверить и убедиться, что ответ действительно верен (или нет). К примеру, если задача заключается в разложении на простые множители числа 11 111 111 111, то вы можете предположить, что одним из множителей является простое число 21 649. Пока это всего лишь догадка, однако ее легко проверить: достаточно разделить исходное число на 21 649 и посмотреть, что получится. Частное равняется 513 239 точно, без остатка. Таким образом, ваша догадка оказалась верной. А если бы я догадался, что делителем должно быть 21 647 — тоже простое число, то деление привело бы к ответу 513 286 с остатком 9069. Таким образом, догадка оказалась бы неверной.

В данном случае правильное предположение можно сделать только чудом или при помощи обмана (я, кстати, прежде чем высказывать «предположение», разложил 11 111 111 111 на простые множители). Но, по существу, мы хотим именно этого. Если бы наша догадка не была чудесной, то можно было бы превратить алгоритм класса NP в алгоритм класса P очень простым способом: нужно было бы делать предположения одно за другим до тех пор, пока одно из них не оказалось бы верным. Мой пример позволяет увидеть, что так не получится: понадобилось бы слишком много попыток. В самом деле, то, что мы пытаемся делать, это всего лишь «пробное деление» на все возможные простые числа до тех пор, пока одно из них не сработает. Из главы 2 мы знаем, что это далеко не лучший способ искать делители.

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

Теперь мы можем сформулировать задачу тысячелетия. Превосходит ли класс NP по размеру класс P или они суть одно и то же? Или короче: равен ли класс P классу NP?

Если ответ «да», то это значит, что существует принципиальная возможность отыскать быстрые и эффективные алгоритмы для автоматического составления расписаний авиарейсов, оптимизации работы завода, выполнения миллиона других важных практических задач. Если ответ «нет», то у нас будет железная гарантия того, что все вроде бы сложные задачи на самом деле сложны, и мы сможем остановиться и не тратить больше времени на поиск быстрых алгоритмов для них. В том и другом случае мы выигрываем. А вот не знать, как в реальности обстоят дела, очень неприятно.

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

Помимо этого, возможны еще два варианта. Не исключено, что можно доказать эквивалентность P и NP, не находя в реальности полиномиальных алгоритмов для каждой конкретной NP-задачи. Математике свойственно предлагать нам неконструктивные доказательства существования: они утверждают, что нечто существует, но не говорят, что оно собой представляет и как его найти. В качестве примеров можно назвать методы проверки на простоту, которые бодро сообщают нам, что данное число не является простым, но не называют ни одного конкретного делителя, или теоремы теории чисел, уверяющие нас, что решения некоего диофантова уравнения ограничены, т. е. не превосходят некоторого предела, но не называющие никакого конкретного ограничения. В конце концов, полиномиальный алгоритм может быть настолько сложным, что записать его, в принципе, невозможно. Тогда естественный пессимизм в отношении бесплатного сыра окажется оправдан даже при положительном ответе на вопрос.

Некоторые исследователи высказываются еще более резко: они считают, что вопрос может оказаться нерешаемым в рамках современной математики, ограниченной формальной логикой. Если так, то невозможно доказать ни да ни нет. Не потому, что мы слишком глупы, чтобы найти доказательство, а потому, что такового не существует. Эта идея появилась на свет в 1931 г., когда Курт Гедель выпустил кошку противоречивости охотиться в стаю философских голубей, населявших подвалы математики (он доказал, что некоторые заявления в арифметике неразрешимы). В 1936 г. Алан Тьюринг нашел неразрешимую задачу попроще — задачу об остановке машины Тьюринга. Всегда ли при заданном алгоритме существует доказательство либо того, что машина остановится, либо того, что она будет считать вечно? Как ни удивительно, ответ Тьюринга был «нет». Для некоторых алгоритмов не существует доказательства ни того ни другого. Не исключено, что задача P/NP окажется такой же. Это объяснило бы, почему никто не может ни доказать, ни опровергнуть соответствующее утверждение. Но никто не может также доказать или опровергнуть утверждение о том, что задача P/NP неразрешима. Может быть, ее неразрешимость сама по себе неразрешима…

Самый очевидный подход к задаче P/NP состоит в том, чтобы выбрать какую-нибудь задачу, о которой известно, что она относится к классу NP, предположить существование полиномиального алгоритма ее решения — и каким-то образом прийти к противоречию. Некоторое время математики пытались применить эту методику к различным задачам, но в 1971 г. Стивен Кук понял, что выбор задачи часто не играет никакой роли. С определенной точки зрения все подобные задачи — с точностью до некоторых технических особенностей — совершенно равноправны. Кук ввел понятие NP-полной задачи. Такая NP-задача обладает следующим свойством: если для ее решения существует алгоритм класса P, то любая NP-задача может быть решена при помощи алгоритма класса P.

Кук нашел несколько NP-полных задач, включая SAT — задачу о выполнимости булевых формул. В ней спрашивается, можно ли сделать заданное логическое выражение истинным при помощи подходящего выбора значений (истинности или ложности) его переменных. Кроме того, он получил более глубокий результат: задача SAT с дополнительными ограничениями (3-SAT) также является NP-полной. Здесь логическая формула должна быть записана в виде «A, или B, или C, или… или Z», где A, B, C…Z — логические формулы, содержащие по три переменные. Спешу добавить, что переменные не обязаны каждый раз быть одними и теми же. Большинство доказательств того, что та или иная задача является NP-полной, восходят к теореме Кука о 3-SAT.

Определение Кука подразумевает, что все 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. Потоковое мышление. Уравнение Навье — Стокса

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

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

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

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

Уравнение Навье — Стокса описывает, как меняется со временем в заданных условиях распределение скоростей в жидкости. О нем часто говорят во множественном числе как об уравнениях Навье — Стокса, но дела это не меняет. Множественное число отражает классический подход: в трехмерном пространстве скорость складывается из трех компонент; в классической теории на каждую компоненту приходится по одному уравнению, а всего их получается три. С современной точки зрения существует всего одно уравнение для вектора скорости (величины, которую характеризует не только размер, но и направление), но это уравнение приложимо к каждой из трех компонент скорости. На сайте Института Клэя используется классическая терминология, но здесь я буду следовать современной практике. Я говорю об этом заранее, чтобы избежать возможной путаницы.

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

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

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

Уравнения сами по себе не имеют особой ценности: их надо еще научиться решать. Для уравнения Навье — Стокса решение означает расчет поля скоростей: скорости и направлении движения жидкости в каждой точке пространства в каждый момент времени. Уравнение налагает ограничения на эти величины, но не определяет их непосредственно. Вместо этого мы должны при помощи этого уравнения соотносить будущие скорости с текущими. Уравнения в частных производных, такие как уравнение Навье — Стокса, имеют много разных решений; точнее говоря, бесконечно много. И это неудивительно: жидкости способны течь очень по-разному: ток жидкости по капоту автомобиля отличается от тока жидкости по крылу самолета в полете. Существует два способа выбрать конкретный поток из бесконечного множества возможностей: используя либо начальные, либо граничные условия.

Начальные условия определяют поле скорости в какой-то конкретный момент времени; обычно его считают нулевым. Физически идея состоит в том, что если вам известно поле скорости в этот момент, то уравнение Навье — Стокса однозначно определяет это поле через очень короткий промежуток времени. Если для начала вы дадите жидкости толчок, она будет двигаться до тех пор, пока это не будет противоречить законам физики. Граничные условия более полезны в большинстве приложений, потому что начальные условия трудно обеспечить в реальной жидкости, да и вообще, они не слишком подходят для применения, скажем, в автомобильном дизайне. Там главное — форма машины. Вязкие жидкости прилипают к поверхностям. Математически это моделируется определением скорости на этих поверхностях, образующих границу занятой жидкостью области, а именно в ней уравнение действительно. К примеру, мы могли бы потребовать, чтобы скорость на границе была нулевой или наложить какое-то другое условие, которое наилучшим образом моделирует реальность.

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

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

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

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

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

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

Уравнения Навье — Стокса настолько точны, что приложимы, судя по всему, даже там, где с точки зрения физики вполне могли бы отказывать: в турбулентном потоке. По крайней мере так дело обстоит в случае, если уравнение может быть решено с достаточной точностью. Главная проблема здесь имеет практический характер: когда поток становится турбулентным, численные методы решения уравнения начинают поглощать громадное количество компьютерного времени. Кроме того, мельчайшие структуры всегда ускользают от «внимания» компьютера.

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

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

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

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

3. Опровержение существования решений в трех измерениях. Опровергнуть пункт 1. Иными словами, найти начальное поле, для которого не существует гладкого решения в любой положительный момент времени, и доказать это утверждение.

4. Опровержение существования решений на трехмерном плоском торе. Доказать, что пункт 2 неверен.

Те же вопросы остаются открытыми и для уравнения Эйлера, которое, в сущности, эквивалентно уравнению Навье — Стокса, но не учитывает вязкости. За ответы на вопросы по уравнению Эйлера, однако, никто никаких призов не обещает.

Серьезная сложность здесь заключается в том, что рассматриваемый поток трехмерен. Существует аналогичное уравнение для жидкости, текущей по плоскости. Физически это может быть либо тонкий слой жидкости между двумя пластинами (считается, что они не вызывают трения), либо такой характер потока в трех измерениях, при котором жидкость движется совершенно идентичным образом вдоль системы параллельных плоскостей. В 1969 г. русский математик Ольга Ладыженская доказала, что для двумерного уравнения Навье — Стокса и двумерного уравнения Эйлера пункты 1 и 2 верны, а 3 и 4 — ложны.

Может показаться удивительным, но для уравнения Эйлера доказательство сложнее, чем для уравнения Навье — Стокса, хотя само уравнение проще, поскольку в нем не учитывается вязкость. Причина, надо сказать, весьма поучительная. Вязкость «снимает» вероятность того, что решение может привести к возникновению сингулярности, а та, в свою очередь, не позволит решению существовать в каждый момент времени. Если условие вязкости отсутствует, этого не происходит, что сказывается на математических характеристиках доказательства существования.

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

Задачи на приз тысячелетия относятся к несжимаемому потоку, поскольку хорошо известно, что сжимаемые потоки ведут себя отвратительно. В уравнениях движения самолета, к примеру, возникает множество проблем, если самолет движется в потоке воздуха быстрее звука. Это знаменитый «звуковой барьер», очень беспокоивший в свое время инженеров, которые работали над проектами сверхзвуковых истребителей. Эта проблема связана с хорошей сжимаемостью воздуха. Если тело движется сквозь несжимаемую жидкость, оно расталкивает частицы этой жидкости в стороны со своего пути, как если бы это были шарики. Если частицы накапливаются, они замедляют тело. Но в сжимаемой жидкости, где существует предел скорости движения волн (а именно скорость звука), этого не происходит. На сверхзвуковых скоростях, вместо того чтобы расходиться в стороны, воздух скапливается перед самолетом, и его плотность там растет беспредельно. Результат — ударная волна. Математически это нарушение непрерывности давления воздуха, которое резко меняет значение на фронте ударной волны. Физически это звуковой удар: громкий хлопок. Ударная волна, если ее не учитывают, может повредить самолет, так что конструкторы волновались не зря. Однако скорость звука — не непреодолимый барьер, а всего лишь препятствие. Ее существование говорит о том, что уравнение Навье — Стокса для сжимаемой жидкости не обязательно имеет гладкие решения на всем диапазоне времен даже в двух измерениях. Так что в этом случае ответ известен заранее, и он отрицателен.

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

Кое-какие положительные результаты для трехмерного уравнения Навье — Стокса уже имеются. Если в начальном состоянии поток характеризуется достаточно маленькими скоростями, т. е. течет вяло и очень медленно, то и первое, и второе утверждения верны. Эти утверждения верны даже при больших скоростях — на протяжении некоторого ненулевого промежутка времени. Неизвестно, существует ли решение, верное для любого момента в будущем, но есть некоторый промежуток времени, на котором решение существует точно. Может показаться, что эту логику рассуждений можно повторять без конца, продвигая решение вперед во времени на небольшие промежутки и используя всякий раз конечный результат как новое начальное состояние. Проблема с подобным подходом заключается в том, что временны́е интервалы при этом могут уменьшаться настолько стремительно, что бесконечное число шагов будет укладываться в конечное время. К примеру, если каждый последовательный шаг продвигает решение на половину времени, достигнутого на предыдущем шаге, то весь процесс закончится за время  что равняется 2. Если решение прекращает существовать — в настоящее время это чисто гипотетическое предположение, но рассматривать его мы все же можем, то говорят, что решение, о котором идет речь, разрушается. Время, за которое это происходит, называется временем разрушения решения.

Так что в четырех задачах, по существу, спрашивается о том, могут ли решения разрушаться. Если не могут, верны утверждения 1 и 2; если могут — утверждения 3 и 4. Возможно, решения могут разрушаться в бесконечном пространстве, а на конечном плоском торе — не могут. Кстати говоря, если ответ на вопрос 1 положителен, то положителен ответ и на вопрос 2, потому что поток любой структуры на плоском торе можно интерпретировать как пространственно периодический поток в целом бесконечном пространстве. Речь идет о том, чтобы наполнить пространство копиями прямоугольника, о котором идет речь, и в каждом воспроизвести поток в точности той же структуры. Правила склеивания для тора гарантируют, что поток, пересекая эти плоские стыки, остается гладким. Аналогично если верно утверждение 4, то верно и утверждение 3 по той же причине. Мы просто делаем начальное пространство пространственно периодическим. Но, насколько мы сейчас в состоянии сказать, ответ на вопрос 2 может оказаться положительным даже при отрицательном ответе на вопрос 1.

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

Это не чисто гипотетические возражения. Примеры подобного сингулярного поведения наблюдаются в некоторых других уравнениях классической математической физики. Замечательный пример можно найти в небесной механике. В 1988 г. Ся Чжихун доказал, что существует такая начальная конфигурация пяти материальных точек, или точечных масс, в трехмерном пространстве, где действует закон тяготения Ньютона, в которой четыре тела через конечный промежуток времени исчезают в бесконечности — тоже своего рода разрушение, а пятое переживает еще более значительные колебания. Ранее Джозеф Гервер указал, что пять тел на плоскости могут все раствориться в бесконечности за конечное время, но не смог завершить доказательство такого сценария. В 1989 г. он доказал, что разбегание такого рода определенно возможно на плоскости, если число тел достаточно велико.

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

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

Почему была выбрана такая извилистая траектория? От каждой встречи с планетой «Галилео» получал энергию и, следовательно, увеличивал скорость. Представьте себе, что космический зонд направляется к планете — не курсом столкновения, но так, чтобы пройти достаточно близко к поверхности и быстро развернуться за ней. После этого его должно вновь выбросить в дальний космос. Когда зонд проходит за планетой, они притягиваются друг к другу. Более того, они все время притягивались друг к другу, но на этой стадии полета сила притяжения становится максимальной и потому производит максимальное действие. Тяготение планеты как бы подталкивает зонд и придает ему дополнительную скорость. Суммарная энергия должна сохраняться, поэтому взамен зонд чуть замедляет движение планеты по орбите вокруг Солнца. Поскольку масса зонда очень мала, а масса планеты, напротив, очень велика, действием зонда на планету можно пренебречь. Действием планеты на зонд пренебречь нельзя: он может ускориться очень заметно.

«Галилео» прошел над поверхностью Венеры на высоте 16 000 км и получил прибавку скорости в 2,23 км/с. После этого он прошел в 960 км от Земли, а затем еще раз в 300 км, во второй раз добавив к своей скорости еще 3,7 км/с. Без этих маневров он не добрался бы до Юпитера, поскольку запускавшая его ракета не смогла бы направить его непосредственно туда. Первоначальный план, кстати говоря, предусматривал именно это: зонд предполагалось запустить на шаттле с кислородно-водородным разгонным блоком Centaur-G. Но катастрофа «Челленджера», когда космический челнок взорвался вскоре после старта, заставила отказаться от этого плана. Использование блока Centaur-G было запрещено. Пришлось воспользоваться для запуска «Галилео» менее мощным твердотопливным блоком IUS. Миссия была весьма успешна, среди ее научных результатов — наблюдение столкновения кометы Шумейкера — Леви с Юпитером, которое произошло в 1994 г., когда зонд был еще на пути к газовому гиганту.

Сценарий Ся учитывает и эффект пращи. Четыре планеты равной массы образуют две тесные пары, которые обращаются вокруг общих центров масс в двух параллельных плоскостях. Эти «ракетки», состоящие каждая из двух тел, играют в звездный теннис пятым, более легким телом, которое носится туда-сюда между ними по траектории, перпендикулярной плоскостям. Система устроена так, что всякий раз, когда этот «теннисный мячик» проходит мимо пары планет, эффект пращи ускоряет его и одновременно отталкивает пару планет прочь вдоль линии, соединяющей обе пары. Таким образом, «теннисный корт» с каждым ударом немного удлиняется, а игроки расходятся дальше. Энергия и импульс сохраняются в равновесии, поскольку две планеты, нанося «удар», придвигаются чуть ближе друг к другу и чуть ускоряют движение вокруг центра масс. При правильных начальных условиях пары планет расходятся все быстрее, и скорость их расхождения растет так стремительно, что они улетают в бесконечность за конечное время. При этом и «теннисный мяч» колеблется между ними все быстрее и быстрее. В сценариях разбегания Гервера тоже используется эффект пращи.

Но приложим ли этот фокус с исчезновением к реальным небесным телам? Нет, если подходить к вопросу буквально. В этих сценариях важно, чтобы тела были материальными точками. Для многих задач из небесной механики это достаточно разумное приближение, но не тогда, когда тела должны проходить на произвольно малых расстояниях друг от друга. Если бы тела конечных размеров действительно так делали, то рано или поздно они непременно столкнулись бы. Кроме того, релятивистские эффекты не позволили бы телам двигаться быстрее света и изменили бы закон гравитации. Во всяком случае начальные условия и дополнительное условие равенства некоторых масс в реальности, вероятно, никогда бы не выполнились. Тем не менее эти любопытные примеры показывают, что, хотя уравнения небесной механики, как правило, очень хорошо моделируют реальность, они могут иметь сложные сингулярности, которые не позволят решениям существовать в каждый момент времени. Не так давно ученые поняли, что в системе тройной звезды, где звезды движутся по сложным траекториям, эффект пращи может в какой-то момент выбросить одну из звезд наружу с большой скоростью. Так что вполне может оказаться, что галактику (а может, и межгалактическое пространство) бороздит несметное количество звезд-сирот — холодных, одиноких, нежеланных и невидимых, изгнанных братьями из своих систем.

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

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

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

Уже исследованы многие сценарии, которые могли бы вести к сингулярностям. Так, в 1941 г. Андрей Колмогоров разработал стандартную на сегодня модель турбулентности в виде каскада бесконечно уменьшающихся вихрей. Он предположил, что на очень мелких масштабах все формы турбулентности выглядят исключительно похоже. Пропорции вихрей заданного размера, к примеру, подчиняются универсальному закону. В настоящее время известно, что по мере уменьшения вихри меняют форму, становятся длиннее и тоньше и образуют элементарные струйки. Из закона сохранения момента импульса следует, что завихренность — степень закрученности вихрей — должна возрастать. Этот процесс называется растягиванием вихрей, и именно такое поведение, в принципе, может привести к сингулярности: к примеру, если мельчайшие вихри растянулись бы и стали бесконечно длинными за конечное время, а завихренность в некоторых точках стала бы бесконечной.

На рис. 43 можно увидеть сильно увеличенное изображение турбулентного потока, смоделированного Пабло Мининни и его коллегами с использованием программы VAPOR — платформы визуализации и анализа для океана, атмосферы и солнечных исследований. На изображениях видна интенсивность завихренности: насколько быстро вращается жидкость. Они иллюстрируют формирование вихревых струек (видны как длинные тонкие структуры) и показывают, что элементарные струйки могут собираться в пучки и образовывать более крупные структуры. Программа позволяет проводить моделирование на кубической решетке более чем с тремя миллиардами узловых точек.

В статье, посвященной этой теме и размещенной на сайте Института Клэя, Чарльз Фефферман написал:

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

Сложность потока на изображениях, подобных рис. 43, помогает представить себе трудности, с которыми, вероятно, столкнутся исследователи в поисках таких идей. Но математики не сдаются — они продолжают идти вперед, пытаясь отыскать простые принципы в видимой сложности.

13. Квантовая головоломка. Массовая щель

В нескольких километрах к северу от Женевы граница между Швейцарией и Францией делает резкий изгиб. На поверхности в этом месте видны лишь проселочные дороги и небольшие деревеньки. Но под землей, на глубине от 50 до 175 м, находится самый крупный на планете научный прибор. Это гигантский кольцевой туннель более 8 км в диаметре, соединенный с другим, меньшим (примерно вчетверо) туннелем. Большая его часть находится под территорией Франции, но две секции приходятся на Швейцарию. По туннелям проложено по паре труб, которые сходятся в четырех точках.