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

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

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

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

Здесь полезно вспомнить о технической интерпретации. Некая проблема должна быть не-P просто потому, что для получения ответа требуется не-P время работы. Например, нам надо составить список всех возможных способов расставить по порядку n символов. Чтобы работать с такой явно не-P проблемой, нужна другая концепция: класс NP недетерминированных полиномиальных алгоритмов. Алгоритм относится к классу NP, если любой предполагаемый ответ можно проверить за время, пропорциональное некоторой фиксированной степени, зависящей от объема вводимых данных. Например, угадав простой множитель большого числа, мы легко можем проверить его одним делением.

Задача из класса 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 в. математики получили доступ к мощному программному оборудованию, позволяющему совершать не только численные расчеты, но и алгебраические и даже аналитические. Эти инструменты открывают новые области, помогают решить давние проблемы и освободить время для глубоких теоретических раздумий. В результате сама математика стала богаче как наука, а ее применение на практике заметно расширилось. У Эйлера было всё теоретически необходимое для изучения протекания потока вокруг сложных форм, и хотя в то время еще не было изобретено воздухоплавание, ученые исследовали многие занимательные вопросы, относящиеся к водным судам. Но у него не было практических методов для полноценной технической реализации своих задумок.

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

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