Текст книги "Квантовые вычисления со времен Демокрита"

Вот тут-то мы и приходим к RP – к классу задач, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью более 1/2, если ответ «да», или с вероятностью нуль, если ответ «нет». Сформулируем иначе: если алгоритм принимает хотя бы раз, то вы можете быть абсолютно уверены, что ответ «да». Если алгоритм отвергает варианты один за другим, то вы можете очень уверенно предполагать (но не гарантировать), что ответ «нет».

У RP есть очевидное «дополнение», называемое co-RP. Это просто класс задач, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью 1, если ответ «да», или с вероятностью менее 1/2, если ответ «нет».

• ZPP (Zero-Error Probabilistic Polynomial-Time, вероятностный, полиномиального времени, с нулевой ошибкой). Этот класс может быть определен как пересечение RP и co-RP – класс задач, относящихся к обоим этим классам одновременно. Можно также сказать, что ZPP – это касс задач, решаемых рандомизированным алгоритмом за полиномиальное время, который обязан выдавать верный ответ всякий раз, когда он его выдает, но в части случаев (до половины) может выдавать ответ «не знаю». Опять же можно дать и такую эквивалентную формулировку: ZPP – это класс задач, решаемых алгоритмом, который никогда не ошибается, но время выполнения которого ожидаемо полиномиальное.

Иногда можно увидеть, как BPP-алгоритмы называют алгоритмы Монте-Карло, а ZPP-алгоритмы – алгоритмы Лас-Вегаса. Мне случалось даже встречать RP-алгоритмы под названием «алгоритмы Атлантик-Сити»[36]36
  Крупные центры игорного бизнеса. – Прим. пер.


[Закрыть]. Такая терминология всегда казалась мне глупой. (Может, существуют еще и алгоритмы индейских резерваций?)

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

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

К счастью, ситуация не настолько неприятна, как кажется: мы по крайней мере знаем, что BPP входит в NP^NP (то есть в NP с NP-оракулом) и, следовательно, во второй уровень полиномиальной иерархии PH. Сипсер, Гач и Лаутеман доказали это в 1983 г. Это доказательство я вообще-то собираюсь пропустить, технически оно достаточно сложное. Если вам интересно, посмотреть можно здесь[37]37
  http://www.cs.berkeley.edu/∼luca/cs278-01/notes/lecture9.ps


[Закрыть].

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

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

Но даже в мире с неоднородностью, уверены специалисты по теории вычислительной сложности, должны существовать серьезные ограничения на то, что может быть эффективно вычислено. Желая поговорить об этих пределах, мы пользуемся терминологией, придуманной Карпом и Липтоном в 1982 г.[38]38
  R. M. Karp and R. J. Lipton, Turing machines that take advice, L'Enseignement Mathematique 28 (1982), 191–209.


[Закрыть] Карп и Липтон определили, класс сложности P/f(n), или P с советом размера f(n), как состоящий из всех задач, решаемых за детерминированное полиномиальное время на машине Тьюринга при помощи f(n)-битной «строки совета» a_n, зависящей только от длины входной строки n.

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

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

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

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

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

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

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

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

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

Ну, здесь можно привести простой аргумент с диагонализацией. Я покажу даже более сильный результат: существуют задачи, не входящие в P/n^{log n}. Пусть M₁, M₂, M₃, … – список полиномиальных по времени машин Тьюринга. Кроме того, зафиксируем длину входной строки n. Я утверждаю, что существует булева функция f: {0, 1}ⁿ → {0, 1}, которую первым n машинам (M₁,…, M_n) не удается вычислить даже при наличии любой n^{log n}-битной строки совета. Почему? Просто посчитаем: существует 2^2ⁿ булевых функций, но только n машин Тьюринга и строк совета. Поэтому выберите такую функцию f для каждого n; при этом каждую машину Mi, ждет неудача при всех длинах, за исключением конечного их числа. Вот и все, нам не потребовалось даже условие, что M_i работает полиномиальное время.

Почему для меня так важен совет? Во-первых, он появляется снова и снова, даже если нас, к примеру, интересуют лишь однородные вычисления. Даже если мы хотим узнать всего лишь, можно ли дерандомизировать BPP, оказывается, что и этот вопрос имеет отношение к совету. Так что совет очень тесно связан с остальными понятиями вычислительной сложности. По существу, можно считать, что алгоритм с советом ничем не отличается от бесконечной последовательности алгоритмов, точно как мы видели в случае теоремы ускорения Блума. Это всего лишь алгоритм, где по мере увеличения длины входной строки вам приходится использовать все новые идеи и добиваться все большего ускорения. Совет можно, в частности, рассматривать так.

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

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

Разумеется, все это время мы с вами танцевали вокруг настоящего вопроса: может ли совет помочь нам в решении задач, которые нас действительно интересуют, таких как NP-полные задачи? В частности, верно ли, что NP ⊂ P/poly? Интуитивно представляется, что вряд ли: булевых формул размера n экспоненциально много, так что если бы вы даже получили каким-то образом от Бога строку совета полиномиального размера, то как бы это помогло вам определить выполнимость больше чем крохотной части этих формул?

Но – и я уверен, что для вас это станет полнейшим шоком, – мы не можем доказать, что это невозможно. Правда, в данном случае у нашего невежества есть хорошее оправдание, поскольку если P = NP, то, очевидно, верно также и NP ⊂ P/poly. Но вот вопрос: если бы нам удалось доказать P ≠ NP, то доказали бы мы тем самым, что NP ⊄ P/poly? Иными словами, следует ли из NP ⊂ P/poly, что P = NP? Увы, мы не знаем ответа даже на этот вопрос.

Но, как и в случае с BPP и NP, ситуация не настолько неприятна, как кажется. Карпу и Липтону все же удалось доказать в 1982 г., что если NP ⊂ P/poly, то полиномиальная иерархия PH схлопывается до второго уровня (то есть до NP^NP). Иными словами, если вы верите, что полиномиальная иерархия бесконечна, вы должны также верить, что NP-полные задачи не решаются эффективно неоднородными алгоритмами.

Эта теорема Карпа – Липтона – самый известный пример очень обширного класса результатов теории вычислительной сложности, класса, который описывают формулировкой «если бы ослы умели свистеть, то свиньи умели бы летать». Иными словами, если бы одна вещь, в истинность которой никто не верит, была бы истинна, то истинна была бы и другая вещь, в истинность которой тоже никто не верит! Интеллектуальный онанизм, говорите? Чепуха! Интересно здесь то, что обе эти вещи, в истинность которых никто не верит, прежде казались совершенно не связанными одна с другой.

Замечание немного не в тему, но доказательство теоремы Карпа – Липтона будет поинтереснее целой бочки карпов. Поэтому рассмотрим его прямо сейчас. Предположим, что NP ⊂ P/poly; нужно доказать, что полиномиальная иерархия схлопнется до второго уровня, или, что эквивалентно, что co-NP^NP = NP^NP. Рассмотрим произвольную задачу в co-NP^NP, примерно такую:

Для всех n-битных строк x существует ли n-битная строка y, такая, что Φ (x, y) дает результат «истина»?

(Здесь Φ – некоторая произвольная полиномиального размера булева формула.)

Нам нужно найти вопрос из NPNP, то есть вопрос, в котором квантор существования идет впереди квантора общности, ответ на который совпадает с ответом на приведенный выше вопрос. Но что это может быть за вопрос? Уловка тут вот в чем: сначала мы используем квантор существования, чтобы угадать полиномиального размера строку совета an. Затем мы используем квантор общности, чтобы угадать строку x. Наконец, мы используем строку совета an, – вместе с предположением, что NP ⊂ P/poly, – чтобы самостоятельно угадать y. Таким образом:

Существует ли строка совета an, такая, что для всех n-битных строк x булева формула φ(x, M(x, a_n)) дает результат «истина»?

Здесь M – это полиномиальная по времени машина Тьюринга, которая при заданном входе x и совете a_n выдает в качестве результата n-битную строку y, такую, что φ(x, y) дает при вычислении «истину» всякий раз, когда такой y существует. По аналогии с одной из задач предыдущей главы мы можем без труда построить такую M при условии, что умеем решать NP-полные задачи в P/poly.

Ну хорошо, я уже рассказывал, что неоднородность тесно связана со случайностью – настолько, что трудно говорить об одной, не упоминая другой. Так что в конце этой главы я хочу рассказать вам о двух моментах, связывающих случайность и неоднородность: о простой связи, открытой Адлеманом в 1970-е гг., и второй, глубокой, которую открыли Импальяццо, Нисан и Вигдерсон в 1990-е гг.

Простая связь заключается в том, что BPP ⊂ P/poly, иными словами, неоднородность по крайней мере столь же мощна, как и случайность. Почему так, как вы считаете?

Ну давайте посмотрим, почему. Имея некоторое BPP-вычисление, первое, что мы делаем, – это усиливаем вычисление до экспоненциально малой ошибки. Иными словами, мы повторяем вычисление, скажем, n² раз, а затем выводим ответ, полученный в большинстве случаев, так что вероятность сделать ошибку падает с 1/3 до примерно 2^-n². (Если вы пытаетесь доказать что-то относительно BPP, усиление до экспоненциально малой ошибки почти всегда представляет собой удачный первый шаг!)

Далее. Сколько существует входных строк длины n? Верно: 2ⁿ. И для каждой входной строки лишь 2^-n² доля случайных строк приводит нас к ошибке. Согласно границе объединения (как мы помним, это самый полезный факт во всей теоретической информатике), из этого следует, что не более 2^n-n² доли случайных строк вообще могут привести нас к ошибке на входных строках длины n. Поскольку 2^n-n²< 1, это означает, что существует некая случайная строка, назовем ее r, которая никогда не вызывает ошибки на входных строках длины n. Так что фиксируем такую r, скармливаем ее в качестве совета машине типа P/poly – и дело сделано!

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

1. Даже если P ≠ NP, вас может заинтересовать, могут ли NP-полные задачи решаться за вероятностное полиномиальное время. Иными словами, входит ли NP в BPP? Понятно, что мы уже можем сказать кое-что конкретное по этому поводу. Если NP ⊆ BPP, то, разумеется, NP ⊂ P/poly (поскольку BPP ⊂ P/poly). Но это означает, что PH схлопывается по теореме Карпа – Липтона. Так что если вы верите, что полиномиальная иерархия бесконечна, то вы верите также, что NP-полные задачи не имеют эффективного решения рандомизированными алгоритмами.

2. Если неоднородность может моделировать случайность, то не может ли она также моделировать квантовость? Иными словами, верно ли, что BQP ⊂ P/poly? Вообще-то мы не знаем, но считается, что скорее всего да. Доказательство Адлемана (что BPP входит в P/poly) полностью рассыплется, конечно, если заменить BPP на BQP. Но это ставит интересный вопрос: а почему оно рассыплется? В чем принципиальная разница между квантовой теорией и классической теорией вероятностей, заставляющая это доказательство работать в одном случае, но не в другом? Я оставлю этот вопрос вам в качестве упражнения.

Ну хорошо, перейдем теперь к глубокой связи. Помните задачу проверки на простоту, о которой речь шла ранее в этой главе? С годами эта задача сползала все ниже и ниже по иерархии сложности, как обезьянка с ветки на ветку:

• Очевидно, что проверка на простоту входит в co-NP.

• В 1975 г. Пратт показал, что она входит в NP.

• В 1977 г. Соловей, Штрассен и Рабин показали, что она входит в co-RP.

• В 1992 г. Адлеман и Хуанг показали, что она входит в ZPP.

• В 2002 г. Аграваль, Кайал и Саксена показали, что она входит в P.

Общий проект по превращению рандомизированных алгоритмов в детерминированные называется дерандомизацией (согласитесь, подобное слово может понравиться только специалисту по теоретической информатике). История задачи проверки на простоту – поистине впечатляющий пример успеха этого проекта. Но с успехом приходит и очевидный вопрос: любой ли рандомизированный алгоритм можно дерандомизировать? Иными словами, верно ли, что P равно BPP?

Опять же мы не знаем ответа на этот вопрос. Обычно, если мы не знаем, равны ли два класса сложности, «по умолчанию» они предполагаются различными. Так было и с P и BPP – зловещая музыка – до последнего времени. Однако в последние полтора десятка лет всё новые появляющиеся свидетельства убедили почти всех нас в том, что P = BPP. Мы не можем здесь сколько-нибудь глубоко разобрать эти свидетельства. Но позвольте мне процитировать одну теорему, просто чтобы показать вам, на что это похоже.

Теорема (Импальяццо – Вигдерсон, 1997)[39]39
  R. Impagliazzo and A. Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In Proceedings of ACM Symposium on Theory of Computing (New York: ACM, 1997), pp. 220–9.


[Закрыть]. Пусть существует задача, решаемая за экспоненциальное время и не решаемая за субэкспоненциальное время даже при помощи строки совета субэкспоненциального размера. Тогда P = BPP.

Обратите внимание, как эта теорема связывает дерандомизацию с неоднородностью и, в частности, с доказыванием того, что определенные задачи трудны для неоднородных алгоритмов. Предположение, безусловно, представляется правдоподобным. С нашей сегодняшней точки зрения вывод (что P = BPP) также представляется правдоподобным. И все же впечатление таково, что они не имеют никакого отношения друг к другу. Так что про эту теорему можно было бы сказать: «Если ослы умеют кричать по-ослиному, то свиньи умеют хрюкать».

Откуда берется эта связь между случайностью и неоднородностью? Она исходит из теории генераторов псевдослучайных последовательностей. Мы познакомимся с псевдослучайными генераторами гораздо подробнее в следующей главе, когда будем говорить о криптографии. Но в основе своей псевдослучайный генератор – это всего лишь функция, принимающая на вход короткую строку (называемую зерном) и выдающая на выходе длинную строку таким образом, что если зерно случайно, то выходная строка выглядит случайной. Очевидно, выход не может быть случайным, поскольку в нем недостаточно энтропии: если зерно имеет длину k бит, то возможных выходных строк может быть лишь 2^k, независимо от их длины. Однако мы хотим лишь, чтобы никакой алгоритм полиномиального времени не мог успешно отличить выход псевдослучайного генератора от «настоящей» случайности. Разумеется, нам также хотелось бы, чтобы функция, превращающая зерно в выходную последовательность, была вычислима за полиномиальное время.

Уже в 1982 г. Энди Яо понял, что если бы можно было создать «достаточно хороший» псевдослучайный генератор, то можно было бы и доказать, что P = BPP. Почему? Ну предположим, что для любого целого k у вас имеется способ растянуть O(log n)-битное зерно в n-битную выходную псевдослучайную последовательность за полиномиальное время таким способом, что никакой алгоритм, выполняющийся за время n^k, не мог бы успешно отличить ее от истинно случайной последовательности. И предположим, у вас есть BPP-машина, работающая за время n^k. В таком случае вы можете просто сделать цикл по всем возможным зернам (которых существует лишь полиномиальное количество), скормить соответствующие выходные данные BPP-машине, а затем выдать в качестве результата ответ, составивший большинство. Вероятность того, что BPP-машина принимает, получив на вход псевдослучайную строку, должна быть примерно равна вероятности того, что она принимает, получив на вход по-настоящему случайную строку, поскольку иначе машина легко отличит случайные строки от псевдослучайных, вопреки нашему предположению!

Но какова во всем этом роль неоднородности? Вот в чем дело: кроме случайной (или псевдослучайной) строки, BPP-машина получает входную строку x. И нам нужно, чтобы дерандомизация работала для всех x. Но это означает, что для целей дерандомизации мы должны думать об x как о строке совета, исходящей от некоего сверхразумного советчика с единственной целью замаскировать псевдослучайный генератор. Понимаете, поэтому-то нам и нужна была задача, трудная даже при наличии совета: нам нужно построить генератор псевдослучайной последовательности, неотличимой от случайной даже в присутствии «советчика» x.

Подведем итоги: если бы мы могли доказать, что определенные задачи достаточно трудны для неоднородных алгоритмов, то мы доказали бы, что P = BPP.

Это ведет нас к третьему различию между BPP и BQP: если большинство специалистов верит, что P = BPP, то опять же большинство определенно не верит, что P = BQP. (В самом деле, мы не можем в это верить, если мы верим, что разложение на простые множители – трудная задача для классических компьютеров.) У нас нет программы «деквантизации», которой можно было бы приписать хотя бы малую долю успеха программы дерандомизации. Опять же создается впечатление, что между квантовой теорией и классической теорией вероятностей существует принципиальная разница, которая позволяет некоторым идеям (таким как идеи Сипсера, Гача и Лаутемана, Адлемана, Импальяццо – Вигдерсона) работать для второй, но не для первой.

Кстати говоря, Кабанец и Импальяццо[40]40
  V. Kabanets and R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13:1/2 (2004), 1–46.


[Закрыть] (и другие) сумели продемонстрировать нечто обратное – в определенном смысле – теоремам дерандомизации. Они показали, что если мы хотим доказать, что P = BPP, то нам придется доказать, что определенные задачи трудны для неоднородных алгоритмов. Это можно воспринимать как своеобразное объяснение причины, по которой никому еще не удалось доказать, P = BPP, хотя это и предполагается. Говоря точнее, дело в том, что если вы хотите доказать, P = BPP, то вам придется доказывать, что определенные задачи трудны, а если вы хотите доказать, что эти задачи трудны, то вы (по крайней мере косвенно) должны будете разбираться с вопросом о P и NP. В теории вычислительной сложности едва ли не любой вопрос в конце концов сходится к проблеме P и NP.