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

5. Палеосложность

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

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

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

• 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 символов, то окажется, что это число растет, как громадная лесенка из экспонент:

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

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

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

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

Аналогично SPACE(f(n)) — это