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

Что я пытаюсь сделать? Я пытаюсь показать вам концептуальную основу Вселенной, прежде чем вывести на сцену квантовую механику. В квантовой механике поразительно то, что она, будучи небрежным эмпирическим открытием, тем не менее меняет некоторые основополагающие вещи! Некоторые не меняет, а некоторые, в общем-то, непонятно, меняет или нет. Но если мы хотим обсудить, как квантовая механика изменила мир, то нам лучше заранее разобраться в том, как он выглядел до появления квантовой механики.

Полезно разбить теорию вычислительной сложности на исторические эпохи:

• 1950-е гг.: поздний тьюрингозой

• 1960-е гг.: заря асимптотического века

• 1971 г.: астероид Кука — Левина; вымирание диагоналозавров

• начало 1970-х гг.: Карпийский взрыв

• 1978 г.: ранний криптозой

• 1980-е гг.: рандомизейская эра

• 1993 г.: извержение вулкана Разборудич; вымирание комбинатавров

• 1994 г.: нашествие квантодактилей

• с середины 1990-х гг. до наших дней: дерандомизейская эра.

Эта глава будет посвящена «палеосложности», то есть теории сложности до появления классов P и NP и NP-полноты, когда на земле царили диагоналозавры. Затем в главе 6 речь пойдет о Карпийском взрыве, в главе 7 — о рандомизейской эре, в главе 8 — о раннем криптозое, а в главе 9 — о нашествии квантодактилей.

Ранее мы говорили о теории вычислимости. Мы видели, что некоторые задачи вычислимыми не являются, к примеру если дано некоторое утверждение о положительных целых числах и требуется сказать, истинно оно или ложно. (Если бы мы могли ответить на этот вопрос, то мы могли бы решить и проблему остановки, что, как мы уже знаем, невозможно.)

А теперь предположим, что у нас есть некоторое утверждение о действительных числах, к примеру такое:

для любых действительных x и y верно

(x + y)² = x² + 2xy + y²,

и мы хотим знать, истинно оно или ложно. В данном случае оказывается, что процедура выяснения ответа на этот вопрос существует, — это доказал Тарский в 1930-е гг., — по крайней мере, когда в утверждении присутствуют только сложение, умножение, сравнение, константы 0 и 1, кванторы общности и существования (но нет экспонент и тригонометрических функций).

Интуитивно понятно, что если все наши переменные принадлежат множеству действительных, а не целых чисел, то все поневоле получится гладким и непрерывным, и невозможно построить такие гёделевские высказывания, как «данное высказывание не может быть доказано».

(Если добавить сюда же экспоненциальную функцию, то, как недавно доказано, у нас по-прежнему не будет способа закодировать гёделевы высказывания с точностью до одной нерешенной задачи в области анализа[23]. Но если мы добавим экспоненциальную функцию и к тому же перейдем от действительных чисел к комплексным, то мы снова сможем кодировать гёделевы высказывания — и теория вновь станет неразрешимой! Понимаете, почему? Ну, если у нас будут комплексные числа, мы сможем принудительно сделать n целым, сказав: мы хотим, чтобы e2πin равнялось 1. И тогда мы вернемся к тому, с чего начинали с целыми числами.)

Но тогда положение воспринималось так: о'кей, мы нашли алгоритм, позволяющий определить истинность или ложность любого высказывания о действительных числах! Можно расходиться по домам! Задача решена!

Беда в том, что если разобраться, сколько шагов требуется этому алгоритму для выяснения истинности высказывания из n символов, то окажется, что это число растет, как громадная лесенка из экспонент: Я читал в биографии[24] Тарского, что когда в 1950-е гг. на сцену вышли реальные компьютеры, первым делом кому-то пришло в голову применить алгоритм Тарского для оценки высказываний о действительных числах. И оказалось, что это безнадежно, мало того, это было бы безнадежно даже для сегодняшних компьютеров! А для компьютеров 1950-х гг. это было безнадежно безнадежно… безнадежно.

Итак, в настоящее время мы говорим о вычислительной сложности. (Или, по крайней мере, это делает большинство из нас.) Идея следующая: вы задаете верхнюю границу некоторого ресурса, который может использовать ваш компьютер. Самые очевидные ресурсы — это (1) время и (2) объем памяти, но можно определить и множество других ресурсов. (На моем сайте Зоопарка cложности[25] вы найдете около 500 вариантов.)

Одно из самых первых открытий состоит в том, что если спросить, сколько можно вычислить за 10 миллионов шагов, или с использованием 20 миллиардов бит памяти, то ничего не выяснишь. Ваша теория вычисления окажется игрушкой произвольного выбора параметров в базовой модели. Иными словами, вы будете заниматься вовсе не теоретической информатикой — вы будете заниматься архитектурой, а это, конечно, бесконечно интересная сама по себе тема, которая никогда не даст вам скучать, но это не наша тема.

Так что вместо этого вам придется задавать более неопределенный вопрос: сколько всего можно вычислить за время, которое растет линейно (или квадратично, или логарифмически) с ростом размеров задачи? Такая постановка вопроса позволит вам игнорировать постоянные коэффициенты.

Итак, определим TIME(f(n)) как класс задач, для которых каждый пример размером n решаем за время, которое растет по линейному закону f(n). Здесь под «решаемым» мы понимаем то, что может решить некоторый конкретный тип идеализированного компьютера (скажем, машины Тьюринга), который мы фиксируем в качестве «опорного». Ключевой эмпирический факт, на который опирается вся теория, состоит в том, что не слишком важно, какой именно тип идеализированного компьютера мы выберем, до тех пор пока мы остаемся в некоторых широких рамках (к примеру, мы рассматриваем только последовательные, детерминистские, классические компьютеры, а не квантовые компьютеры или еще что-то подобное).

Аналогично SPACE(f(n)) — это класс задач, решаемых нашей опорной машиной с использованием объема памяти (пространства), растущего по линейному закону f(n).

Что можно сказать о взаимоотношениях между этими классами? Понятно, что для любой функции f(n) TIME(f(n)) содержится в SPACE(f(n)). Почему? Потому что за один шаг по времени машина Тьюринга может получить доступ максимум к одной ячейке памяти.

Что еще? Вы, надо понимать, согласны, что TIME(n²) входит в TIME(n³). Вот вам вопрос: оно заключено строго внутри? Иными словами, можно ли решить за время n³ больше задач, чем за время n²?

Оказывается, можно. Это следствие фундаментального открытия, получившего название теоремы об иерархии (по времени); эту теорему доказали Хартманис и Штернс в середине 1960-х гг., за что были удостоены премии Тьюринга. (Не хочу принизить их вклад в науку, но тогда премия Тьюринга котировалась не особенно высоко! Конечно, чтобы ее добиться, нужно было знать о существовании премии, а знали о ней немногие.)

Посмотрим, как это доказывается. Нужно найти задачу, решаемую за время n³, но не за n². Что это может быть за задача? Это простейшая вещь, какую только можно себе представить: ограниченный во времени аналог проблемы остановки Тьюринга.

Пусть M — машина Тьюринга; остановится ли M не более чем за n^2,5шагов? (Здесь n^2,5 — всего лишь некоторая функция, лежащая между n² и n³.)

Ясно, что мы можем решить приведенную задачу за n³ шагов, промоделировав M на n^2,5 шагов и посмотрев, остановится она или нет. (Более того, мы можем решить эту задачу за что-то вроде n^2,5 log n шагов. Конечно, при моделировании нам всегда нужен какой-то запас, но его можно сделать чрезвычайно маленьким.)

А теперь предположим, что существует программа P, способная решить эту задачу за n² шагов, и придем к противоречию. Ясно, что, используя P как подпрограмму, мы могли бы получить новую программу P′, которая ведет себя следующим образом. Получив программу M на вход, P′

1. Работает до бесконечности, если M останавливается не более чем через n^2,5, получив на вход собственный текст, или

2. Останавливается через n^2,5 шагов, если M делает больше, чем n^2,5 шагов, получив на вход свой собственный текст.

Кроме того, P′ делает все это не более чем за n^2,5 шагов (точнее, за n² шагов плюс некоторая добавка).

Что мы делаем дальше? Ну конечно, подаем P′ на вход ее собственный текст! И обнаруживаем, что P′ должна делать противоположное тому, что делает сейчас: работать вечно, если останавливается, или останавливаться, если работает вечно. Это дает нам противоречие, из которого следует, что P вообще не может существовать.

Очевидно, выбор между n³ и n² не имеет особого значения. Можно поставить вместо этого выбор между n¹⁷ и n¹⁶, между 3ⁿ и 2ⁿ и т. п. Но тут возникает интересный вопрос: можно ли подставить сюда любые функции f и g, такие, что f растет значительно быстрее g? Удивительно, но ответ — нет! Функция g должна обладать свойством, известным как конструируемость во времени, которое означает (в основном), что существует некоторая программа, которая останавливается за g (n) шагов, получив на вход n. Без этого свойства программа P′ не знала бы, на сколько шагов нужно моделировать M, и доказательство бы не прошло.

Вообще говоря, любая функция, которая может вам встретиться в обычной жизни, будет конструируемой во времени. Но в начале 1970-х гг. специалисты по теории вычислительной сложности придумали несколько необычных, стремительно растущих функций, которые не являются таковыми. И для этих функций вы реально можете получить произвольно большие прорехи в иерархии вычислительной сложности! К примеру, существует функция f, такая, что TIME(f(n)) = TIME(2f⁽ⁿ⁾). Бреееед.

Аналогом теоремы иерархии (по времени) является теорема иерархии (по памяти), которая утверждает, что существует задача, решаемая при наличии n³ бит памяти, но не решаемая при наличии n² бит.

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

В противоположность тому, что вы могли бы подумать, это не просто теоретический кабинетный вопрос — это конкретный, очень практический кабинетный вопрос! В качестве примера рассмотрите задачу перемножения двух матриц n × n. Очевидный алгоритм занимает время O(n³). В 1968 г. Штрассен предложил более сложный алгоритм, занимающий время O(n^2,78). За этим последовала длинная цепь улучшений, кульминацией которой стал алгоритм Копперсмита и Винограда с оценкой O(n^2,376). После этого 23 года ничего не менялось, пока в 2011 г., незадолго до того, как эта книга отправилась в печать, Стозерс[26] и затем Василевская[27] объявили об улучшениях, дающих алгоритм с оценкой O(n^2,373). Но конец ли это? Может быть, существует алгоритм перемножения матриц за время порядка n²? Или более странная возможность: может ли быть, что для любого ε > 0 существует алгоритм перемножения матриц n × n за время O(n^2+ε), но по мере приближения ε к нулю эти алгоритмы становятся все более и более сложными, и так до бесконечности?

Понимаете, кое-что в материале о палеосложности по-настоящему нетривиально! (Может, тираннозавр рекс и был динозавром, но зубы у него были весьма острые!) В данном случае имеется результат 1967 г., известный как теорема ускорения Блума, который утверждает, что задачи, для которых нет самого быстрого алгоритма, действительно существуют. И не только это: существует задача P, такая, что для любой функции f, если для P имеется алгоритм на O(f(n)), для нее имеется также алгоритм на O(log f(n))!

Посмотрим, как это происходит. Пусть t(n) — оценка вычислительной сложности. Наша цель определить функцию f на множестве целых чисел со значениями в {0, 1}, такую, что если f может быть вычислена за O(t(n)) шагов, то она может быть вычислена также за O(t(n — i)) шагов для любого положительного целого i. Тогда, считая, что t растет достаточно быстро, получаем сколь угодно сильное ускорение: к примеру, если мы зададим t(n):= 2^t(n–1), то с определённостью t(n — 1) = O(log t(n)).

Пусть M₁, M₂,… будет упорядоченным списком машин Тьюринга. Далее, пусть S_i = {M₁, …, M_i} — множество, состоящее из первых i машин. Вот что мы делаем: получая на вход целое n, мы проходим по всем i от 1 до n. На i-й итерации мы моделируем все машины в Si, не «вычеркнутые» на итерациях от 1-й до (i — 1) — й. Если ни одна из этих машин не останавливается не более чем за t(n — i) шагов, то задаем f(i) = 0. В противном случае пусть M_j будет первой машиной, которая остановится не более чем за t(n — i) шагов. Затем определяем f(i) как 1, если M_j выдает 0, и как 0, если Mj выдает 1. (Иными словами, мы заставляем M_j ошибиться при вычислении f(i).) Мы также «вычеркиваем» M_j в том смысле, что M_j не нужно будет моделировать в дальнейших итерациях. Так определяется функция f.

Конечно, f(n) можно вычислить за O(n²t(n)) шагов, просто смоделировав всю описанную выше итеративную процедуру. Ключевое наблюдение таково: для любого целого i, если мы жестко пропишем результат итераций с 1-й по i-ю в наш алгоритм моделирования (то есть сообщим алгоритму, какие M_j вычеркиваются в этих итерациях), мы можем пропустить итерации 1… i и перейти сразу к итерации i + 1. Более того, считая, что мы начинаем с итерации i + 1, мы можем вычислить f(n) всего за O(n²t(n — i) шагов вместо O(n²t(n)) шагов. Так что чем больше информации мы вычислим предварительно, тем быстрее алгоритм будет работать при достаточно больших входных n.

Чтобы превратить эту идею в доказательство, главное, что нужно сделать, — это показать, что моделирование итеративной процедуры — практически единственный способ вычислить f, или, более точно, что любой алгоритм вычисления f требует по крайней мере t (n — i) шагов для некоторых i. Это, в свою очередь, подразумевает, что для вычисления f не существует более быстрых алгоритмов.