Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Сложность вычислений (Н. К. Верещагин, В. Н. Крупский, А. Шень)

Существование компьютерной программы вычисления функции f(x) ещё не означает возможности её вычисления на практике. Например, алгоритм распознавания простоты натурального числа x, имеющего n десятичных знаков, с помощью решета Эратосфена требует перебора 10n/2 возможных делителей x. Предположим, что этот алгоритм выполняется на компьютере с тактовой частотой 1015 Гц (частота атомных переходов). Тогда для проверки простоты 46-значного числа потребуется не меньше 108 секунд, что примерно равно трём годам!

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