Квантовые вычисления со времен Демокрита - Скотт Ааронсон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Понимаете, кое-что в материале о палеосложности по-настоящему нетривиально! (Может, тираннозавр рекс и был динозавром, но зубы у него были весьма острые!) В данном случае имеется результат 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):= 2t(n–1), то с определённостью t(n — 1) = O(log t(n)).

Пусть M1, M2,… будет упорядоченным списком машин Тьюринга. Далее, пусть Si = {M1, …, Mi} — множество, состоящее из первых i машин. Вот что мы делаем: получая на вход целое n, мы проходим по всем i от 1 до n. На i-й итерации мы моделируем все машины в