Йэн Стюарт - Укрощение бесконечности. История математики от первых чисел до теории хаоса [litres]

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

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

Численный расчет обтекания воздухом движущегося самолета

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

Проблему «P = NP?» усугубляет загадочный феномен, получивший название NP-полной задачи. Многие задачи NP таковы, что если они действительно сводятся к классу P, то и любая другая задача из NP сводится к классу P. Такая задача и называется NP-полной . Если для конкретной NP-полной задачи может быть доказано, что она является P, то P = NP. А если для некоторой NP-полной задачи может быть доказано, что она не-P, то P – не то же, что NP. Одной из NP-полных задач, недавно привлекшей внимание ученых, была задача, связанная с популярной компьютерной игрой «Сапер». В математической интерпретации она известна как задача выполнимости булевых формул: есть некое высказывание математической логики; будет ли оно истинным, если присвоить значения «истина» или «ложь» ее переменным?

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

Вычислительные машины – не просто «обслуживающий персонал» для математиков. Их проектирование и работа с ними поставили перед учеными новые теоретические вопросы. Последние варьируют от обоснования приближенных численных методов решения уравнений до более глубоких аспектов основ вычислений.

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

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