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

Численные методы

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

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

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

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

Глава 20. Хаос и сложность

Упорядоченный беспорядок

К середине XX в. математика вступила в фазу стремительного роста благодаря ее активному применению на практике и появлению новых мощных методов. Достоверная история современной математики займет не меньше места, чем перечисление всех ее предшествовавших достижений. Остается выбрать лишь самые выразительные примеры, чтобы показать, что математики по-прежнему отличаются оригинальностью и творческим мышлением. Одной из таких тем, привлекавших пристальное внимание широкой публики в 1970–1980-х гг., является теория хаоса (так называют СМИ нелинейную динамику).