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

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

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

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

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

ЧТО ЧИСЛЕННЫЕ МЕТОДЫ ДАЮТ НАМ

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

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

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