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

задач, относящихся к обоим этим классам одновременно. Можно также сказать, что ZPP — это касс задач, решаемых рандомизированным алгоритмом за полиномиальное время, который обязан выдавать верный ответ всякий раз, когда он его выдает, но в части случаев (до половины) может выдавать ответ «не знаю». Опять же можно дать и такую эквивалентную формулировку: ZPP — это класс задач, решаемых алгоритмом, который никогда не ошибается, но время выполнения которого ожидаемо полиномиальное.

Иногда можно увидеть, как BPP-алгоритмы называют алгоритмы Монте-Карло, а ZPP-алгоритмы — алгоритмы Лас-Вегаса. Мне случалось даже встречать RP-алгоритмы под названием «алгоритмы Атлантик-Сити»[36]. Такая терминология всегда казалась мне глупой. (Может, существуют еще и алгоритмы индейских резерваций?)

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

Вас, может быть, удивит, но мы до сих пор не знаем, входит ли BPP в NP. Но подумайте: даже если бы BPP-машина принимала с вероятностью, близкой к 1, как бы вы доказали это детерминированной программе-верификатору за полиномиальное время, вовсе не склонной вам верить? Конечно, вы могли бы показать верификатору некоторое количество случайных прогонов машины, но и после этого она бы продолжала подозревать вас в том, что вы специально подобрали образцы так, чтобы получить желаемый ответ.

К счастью, ситуация не настолько неприятна, как кажется: мы по крайней мере знаем, что BPP входит в NPNP (то есть в NP с NP-оракулом) и, следовательно, во второй уровень полиномиальной иерархии PH. Сипсер, Гач и Лаутеман доказали это в 1983 г. Это доказательство я вообще-то собираюсь пропустить, технически оно достаточно сложное. Если вам интересно, посмотреть можно здесь[37].

Кстати говоря, если мы знаем, что BPP входит в NPNP, то относительно BQP мы ничего такого не знаем. BQP — это класс задач, решаемых за полиномиальное время на квантовом компьютере. BQP в этой книге пока официально не представлен, — вам придется подождать еще пару глав! — но я хочу предвосхитить в какой-то степени его появление и рассказать, чем он, судя по всему, не является. Иными словами, что, как нам известно, верно в отношении BPP такого, о чем мы не можем сказать, верно ли оно в отношении BQP? Включение в PH — это лишь первый из трех примеров, с которыми мы познакомимся в этой главе.

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

Но даже в мире с неоднородностью, уверены специалисты по теории вычислительной сложности, должны существовать серьезные ограничения на то, что может быть эффективно вычислено. Желая поговорить об этих пределах, мы пользуемся терминологией, придуманной Карпом и Липтоном в 1982 г.[38] Карп и Липтон определили, класс сложности P/f(n), или P с советом размера f(n), как состоящий из всех задач, решаемых за детерминированное полиномиальное время на машине Тьюринга при помощи f(n) — битной «строки совета» an, зависящей только от длины входной строки n.

Вы можете думать о полиномиальной по времени машине Тьюринга как об аспиранте, а о строке совета an как о мудрости его научного руководителя. Как и большинство руководителей, он бесконечно мудр, благожелателен и надежен. Он ничего так не жаждет, как помогать своим аспирантам решать проблемы с их диссертациями, то есть определять, являются ли их входные строки x из {0, 1}n да-строками или нет-строками. Но, опять же как большинство научных руководителей, он слишком занят, чтобы выяснять, над какими конкретно задачами работают в данный момент его аспиранты. Поэтому он просто выдает им всем один и тот же совет an, позволяя каждому применить его к своим входным данным x.

Можно было бы изучить совет, который не заслуживал бы доверия, и я в свое время занимался этим. Я определил несколько классов сложности, основанных на совете, не заслуживающем доверия, но в обычном определении совета мы считаем, что он доверия заслуживает.

Нам будет особенно интересен класс P/poly, который состоит из всех задач, решаемых за полиномиальное время с использованием совета полиномиального размера. Иными словами, P/poly есть объединение P/nk по всем положительным целым k.

Далее, возможно ли, что P = P/poly? В качестве первого (тривиального) наблюдения я заявляю: ответ «нет» — P строго содержится в P/poly и, более того, в P/1. Иными словами, даже с единственным битом совета вы в состоянии сделать больше, чем вообще без совета. Почему?

Верно! Рассмотрим следующую задачу:

Если задана входная строка длиной n, определите, остановится ли n-я машина Тьюринга.

Мало того, что эта задача не входит в P, она даже не является вычислимой, ведь она представляет собой не что иное, как медленное, «унарное» шифрование проблемы остановки. С другой стороны, ее легко решить при помощи единственного бита совета, который зависит только от длины входной строки n. Ибо этот бит совета способен просто сказать вам, чему равен ответ!

Вот еще один способ понять мощь совета: если число задач в P — всего лишь счетная бесконечность (почему?), то число задач в P/1 — бесконечность уже несчетная (почему?).

С другой стороны, один тот факт, что с советом можно решить намного-намного больше задач, чем без него, не означает, что совет поможет вам решить любую конкретную задачу, которая вас, возможно, интересует. В самом деле, второе несложное наблюдение состоит в том, что совет не всемогущ: существуют задачи, не входящие в P/poly. Почему?

Ну, здесь можно привести простой аргумент с диагонализацией. Я покажу даже более сильный результат: существуют задачи, не входящие в P/nlog n. Пусть M1, M2, M