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

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

Все современные цифровые компьютеры работают на двоичной системе, где числа представляются последовательностями всего двух цифр: 0 и 1. Главное преимущество двоичной системы – в ее соответствии переключению: 0 – выключено, 1 – включено. Или 0 – нет напряжения, а 1 – это пять вольт или какой-то иной вариант, используемый в схеме проектирования. Символы 0 и 1 могут также быть интерпретированы в рамках математической логики как значения истинности : 0 означает ложь, 1 – истина. Иными словами, компьютеры могут выполнять логические вычисления так же, как и арифметические. Конечно, логические операции здесь базовые, а арифметические можно рассматривать как последствия логических. Алгебраический подход Буля к математике 0 и 1, изложенный в его «Исследовании законов мышления», обеспечивает эффективный формализм для логики компьютерных вычислений. Поисковые системы интернета выполняют булевы логические запросы: ищут ответы, определенные некоторой комбинацией логических критериев, такие как «содержит слово “кошка”, но не содержит слово “собака”».

Математика внесла свой вклад в компьютерную науку, но и компьютерная наука подтолкнула к открытию поразительной новой математики. По одному из определений, алгоритм – систематический порядок действий для решения задачи. Это слово восходит к арабскому ученому Аль-Хорезми. И тут возникает любопытный вопрос: как зависит время работы алгоритма от объема вводимых данных?

Например, алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел m и n , где m ≤ n , выглядит так.

• Разделить n на m и получить остаток r .

• Если r = 0, то наибольший общий делитель – m : СТОП.

• Если r > 0, тогда заменить n на m , а m на r и вернуться к началу.

Можно показать, что если m включает d десятичных цифр (мера объема вводимых данных для алгоритма), то алгоритм останавливается максимум после 5 d шагов. Это значит, в частности, что если нам заданы два числа с 1000 цифр, то мы можем вычислить их наибольший общий делитель не более чем за 5000 шагов – на что современному компьютеру требуется доля секунды.

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

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

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

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